Ускорьте поиск TCL для длинного списка длинных строк

Question

Я загружаю файлы с символами подстановки в файловой системе.Чтобы избежать двойного счета, я использую список уже захваченных файлов, а затем проверяю их.Теперь имена полных путей к файлам довольно длинные, и я перехожу к тысячам файлов.Поиск в lsearch становится очень медленным.

В упрощенной версии это выглядит так.Что можно сделать, чтобы улучшить это?Я думал сделать строки короче, используя какую-то CRC и поместив это в готовый список.Но вычисление отпечатка пальца не должно занять больше времени, чем поиск.

Answer 1

Существует два варианта, при условии, что вас всегда интересует, присутствует ли буквальная строка или нет (что мне кажется вероятным, поскольку шаблоны исходят из glob):

1. Если вы можете убедиться, что список, по которому вы ищете, отсортирован по алфавиту, lsearch -sorted намного быстрее (O (log n) по размеру данных, а не O (n); он выполняет двоичный поиск).Единовременная стоимость сортировки списка может быть оправдана.

2. Если вас действительно волнует, присутствует ли значение или нет, вы можете загрузить записи списка в словарь или массив как:ключи;проверка наличия значения (dict exists или info exists) - очень дешевая операция, даже с большим количеством данных.Под обложками, dicts и массивы - это хеш-таблицы, и поэтому они очень подходят для такого рода вещей.

Если вы строите список по частям в качестве проверки против повторения работы (звучит каквы), тогда вариант 2 является абсолютно лучшим.

Answer 2

Чтобы выполнить предложение Донала:

вы можете загрузить записи списка в словарь или массив в виде ключей

set d [dict create {*}[string cat [join [glob {*}$patterns] " _ "] " _"]]
foreach fn [dict keys $d] {
  puts $fn
}

• glob может работать с несколькими шаблонами одновременно, не нужно вводить только один шаблон за раз.
• Создать список элементов четного размера (его строковое представление) из результатов глоба, используя join.
• Загрузить результирующую строку rep списка Tcl в словарь, используя dict create.
• Используйте dict keys для получения (уникального) списка ключей.

Answer 3

Я нашел лучшую идею сначала добавить все в список, а затем в конце uniquify.Таким образом, требуется только один проход по списку.

set all_fn {}
foreach fn $files {
    regsub {stuff} $fn {stuff_with_wildcards} pattern
    set all_fn [concat $all_fn [ glob $pattern ] ]
}
set all_fn_u [ lsort -unique $all_fn ]
foreach fn $all_fn_u {
    #Do something with $fn
}