1. Mikhail Korobov
  2. pymorphy
  3. Issues
Issue #29 wontfix

Ускорение через дополнительный индекс

Mikhail Korobov
repo owner created an issue

Юра Бабуров выслал очень интересный патч по этому поводу, ускорение до 17тыс разборов в секунду ценой небольшого увеличения памяти и времени запуска.

Comments (4)

  1. Mikhail Korobov reporter

    Смена структуры данных в словарях, чтоб ускорить наиболее частые выборки. See #29. При этом сломались тесты на склонение, т.к. порядок правил имел значение, а теперь стал неопределенным.

    2415fee6cce9

  2. Mikhail Korobov reporter

    Тесты все работают.

    В оригинальном патче строился отдельный доп. индекс по суффиксам правил.

    Я пошел немного другим путем: поменял структуры данных. В rules вместо массива tuple теперь словари, чтоб ускорить наиболее частую выборку:

    {paradigm_id -> {suffix: [(ancode, prefix, index)]} }
    

    index тут - чтоб не терять информацию о порядке правил.

    endings пришлось поменять, т.к. "индекс правила" смысл теряет, для парадигмы прямо правила записываются

    {word_end->{paradigm_id->tuple(possible_rules)}}
    

    Т.е. в патче предлагалось по суффиксу выбрать номер парадигмы и информация о суффиксе дублировалась (он был как в парадигме, так и в доп. индексе). В закоммиченном варианте код сначала берет номер парадигмы, потом для каждой смотрит, есть ли нужный суффикс в этой парадигме; суффиксы записаны в одном месте (ключи словаря правил в парадигме).

    Но, возможно, я тут не прав, и смотреть сначала суффикс может оказаться лучше, т.к. у словарей время доступа O(1) и без разницы, искать ли в большом словаре или маленьком. А если суффиксы все поместить в один словарь (а не в отдельные словари для каждой парадигмы), то потом потенциально можно сэкономить память, заменив словарь на trie какой-нибудь. Поэтому тикет оставляю открытым.

  3. Log in to comment