Быстрая структура данных в Python для индексации множества изображений в виде дубликатов - PullRequest
Новая
       58

Быстрая структура данных в Python для индексации множества изображений в виде дубликатов

1 голос
/ 15 апреля 2019

Введение: Я хочу заменить около 280 000 изображений математических формул в Энциклопедии математики их соответствующими TEX-кодами.Чтобы сделать это, я классифицировал все эти изображения (или, лучше: их URL) в список из 100 000 списков.

Каждый «подсписок» содержит строки URL-адресов, так что каждый URL-адрес в этом подсписке ссылается нато же изображение.Список выглядит примерно так: [["https://www.encyclopediaofmath.org/legacyimages/a/a130/a130010/a1300105.png", "https://www.encyclopediaofmath.org/legacyimages/a/a010/a010080/a01008021.png", ...], ["https://www.encyclopediaofmath.org/legacyimages/w/w130/w130080/w1300801.png", "https://www.encyclopediaofmath.org/legacyimages/w/w130/w130080/w130080211.png"], ...].

Для каждого подсписка я (или все еще в процессе) определил соответствующий код TEX для одного изображения этого подсписка.Поскольку изображения в каждом подсписке идентичны, я (или до сих пор) определил код TEX для каждого URL-адреса изображения во всем списке.

Теперь я хочу заменить изображения в каждой статье (например, этот ) по известному коду TEX.Это приводит к тому, что мне приходится индексировать URL-адреса изображений для каждой статьи в этом списке подсписков.

Мой вопрос: Знаете ли вы какие-либо структуры данных лучше, чем список списков для вышеtask?

Пример кода: 

dups = [[i, i+1] for i in range(100000)]
for i in range(10000):
    for j in range(100000):
        if i in dups[j]:
            print(f"Found number {i} in {j}-th list")
            break

В приведенном выше примере dups - это упрощенная версия моего списка списков (и вместо этого я использую числастрок.) Как вы можете заметить, приведенная выше программа требует некоторого времени для завершения.Я хотел бы улучшить дублирование, чтобы подобный тип индексации можно было выполнять быстрее.

Примечание 1: Приведенный выше код по существу выполняет сравнения 1 + 2 + 3 + ... + nесли дупс имеет длину п.Это приводит к n * (n + 1) / 2 сравнений.Поскольку в моем случае n = 100'000, это уже много сравнений.

Замечание 2: Очевидным улучшением было бы преобразование каждого подсписка в набор Python и рассмотрениесписок комплектов.Однако большинство моих подсписков содержат менее 3 изображений, поэтому я сомневаюсь, что это значительно улучшит время выполнения.

Примечание 3: Обратите внимание, что я едва могу контролировать порядок "входящих"изображения (в основном я должен следовать структуре статьи) и что я не могу создать полный порядок внутри списка списков (так как я не могу разбить подсписки на части.) Таким образом, я не нашел способ реализовать бинарный поиск.

1 Ответ

1 голос
/ 15 апреля 2019

Хотя это может привести к избыточности данных, я бы предложил использовать двоичное дерево поиска. Ваш список списков - хорошая идея для индексирования, но у него есть одна существенная проблема, которая действительно является временем выполнения.

Ваша метрика для дерева может быть просто буквенным сравнением ссылок (a z и т. Д.). Таким образом, по сути, у вас есть бинарный поиск и просто некоторые избыточные данные. Если мы посчитаем, у вас будет 280 000 изображений, что означает, что среднее время поиска в BST будет log[2](280,000), что составляет приблизительно 18 шагов. То, что у вас есть примерно три одинаковых TEX-кода, на самом деле не имеет значения, учитывая улучшение скорости, просто сохраните его 3 раза. Относитесь к нему как к паре ключ и значение. В вашем BST ключом является ваша ссылка, соответствующее значение просто сохраняется вместе с ней (для которой вы можете использовать свой список списков). Вы также можете указать значение вашей пары в качестве индекса подсписка, в котором она находится. Но мое общее предложение будет игнорировать ваши подсписки при поиске и использовать их снова, когда вы закончите с ним.

Дерево будет выглядеть примерно так: 

                                (link, code/index)
                              /                     \
                      (link,code/index)       (link, code/index)
                            / \                      / \
                            etc.                     etc.

Если вы хотите или должны придерживаться идеи своего подсписка, тогда я могу только предложить создать dictionary на основе ваших списков. См. Здесь 1010 * сложность времени того.

Хотя, если возможно, я бы реализовал это на языке с указателями или таким образом, чтобы ваш код для каждой ссылки был одним и тем же объектом для экономии места.

...