А не пофиг?

Сколько строк в списке? Думаю, пока не будет несколько десятков тысяч - все равно как.

Количество может быть различно. У меня на компе около 400.

>У меня на компе около 400.
это совсем не серьезно. Зачем вообще ставишь перед собой лишние проблемы?
Теоретически быстрее сравнивать напрямую, вычисление хешей - дополнительная нагрузка и память, плюс все равно придется сравнивать.

Надо по полученной строке найти .desktop файл

т.е. там имена файлов? Тебе любой .desktop нужен или с определенным именем? Если первое, то по хешам ничего не найдешь.

Есть словарь вида 'exec строка из desktop файла':'desktop файл'.
Вот по этому и надо искать, т.е. по ключу в словаре.

быстрее сравнивать поразрядно (man radix trees, читать Сэджвика)

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

эффективные реализации поразрядных деревьев: trie, patricia, ternary search tree

да что там, посмотрите хотя бы на красно-чёрные деревья(red-black tree) которые в std::map используются (не знаю что там в питоне :), но их сравнительно легко заимплементить), всё эффективнее

хэш хорош когда используется сравнительно короткие ключи

1) Преждевременная оптимизация - корень всех бед.

2) Вместо того, чтобы слушать советы велосипедистов с ЛОРа берите профайлер и измеряйте.

Преждевременная оптимизация - корень всех бед.

преждевременная пессимизация - не меньшее зло

>Я вот думаю, может их все хешировать?

А если попробовать не думать и использовать встроенный питоновский dict, который вроде как представляет из себя хэш-таблицу?

+1

Макконнелл рулит, согласен.

>берите профайлер и измеряйте.
по-моему автор просто херней страдает. Какие к черту профайлеры и оптимизации на банальном поиске в файле из 400 строк?

берите профайлер и измеряйте.

по-моему автор просто херней страдает. Какие к черту профайлеры и оптимизации на банальном поиске в файле из 400 строк?

херней страдают в каментах, имхо, задача 100500 тыщ раз уже обсосанная и описанная

и ничего там профайлинг не даст умного, максимум позволит подкрутить эффективность алгоритма

банальный поиск в файле из 400 строк порой может закончиться не менее банальным поиском в файле из 2 млн. строк или, к примеру, банальнейщим разбором файла в 450 Мб

банальный поиск в файле из 400 строк порой может закончиться не менее банальным поиском в файле из 2 млн. строк или, к примеру, банальнейщим разбором файла в 450 Мб

Вот когда проблема появится, тогда её и нужно начинать решать.

банальный поиск в файле из 400 строк порой может закончиться не менее банальным поиском в файле из 2 млн. строк или, к примеру, банальнейщим разбором файла в 450 Мб

Вот когда проблема появится, тогда её и нужно начинать решать.

ээээ нет, так дела не делаются, «потом» может не быть времени

почему бы сразу не реализовывать правильные решения, с учётом того что сложность реализации одинаковая?

поиск элемента массива - линейное время, получение элемента хеш-массива - константа.

Хеш лучше.

ээээ нет, так дела не делаются, «потом» может не быть времени

Поиск среди 400 строк, 2 млн. строк и в файле 450 мб требуют применения трёх разных методов. О чём речь? Может, ещё фреймворк написать?

> А если попробовать не думать и использовать встроенный питоновский dict, который вроде как представляет из себя хэш-таблицу?

+100500

ээээ нет, так дела не делаются, «потом» может не быть времени

Поиск среди 400 строк, 2 млн. строк и в файле 450 мб требуют применения трёх разных методов.

отнюдь, с чего бы?

О чём речь? Может, ещё фреймворк написать?

если это обосновано, то почему бы и нет

Поиск среди 400 строк, 2 млн. строк и в файле 450 мб требуют применения трёх разных методов.

отнюдь, с чего бы?

С того, что для первого случая вообще заморачиваться не нужно, столько процессорного времени не сэкономишь, сколько своего (несравнимо более дорогого!) потратишь. Для второго случая стоит подумать, но это решение для третьего будет не оптимальным.

Поиск среди 400 строк, 2 млн. строк и в файле 450 мб требуют применения трёх разных методов.

отнюдь, с чего бы?

С того, что для первого случая вообще заморачиваться не нужно, столько процессорного времени не сэкономишь, сколько своего (несравнимо более дорогого!) потратишь. Для второго случая стоит подумать, но это решение для третьего будет не оптимальным.

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

Вы ж не думаете что задача ТС - это очень сложный случай, не встречавшийся ни у кого ранее?

Вы ж не думаете что задача ТС - это очень сложный случай, не встречавшийся ни у кого ранее?

Я думаю, что задача ТС - такая фигня, на реализацию которой нужно меньше времени, чем на написание этого поста.

Вы ж не думаете что задача ТС - это очень сложный случай, не встречавшийся ни у кого ранее?

Я думаю, что задача ТС - такая фигня, на реализацию которой нужно меньше времени, чем на написание этого поста.

задача - возможно, но вопрос ТС был потоньше - как быстрее сравнивать строки и тут имхо всё прозрачно

задача - возможно, но вопрос ТС был потоньше - как быстрее сравнивать строки и тут имхо всё прозрачно

Разве? Сравнивать строки по 10 символов и 10 млн. символов - совершенно подходы к решению :)

задача - возможно, но вопрос ТС был потоньше - как быстрее сравнивать строки и тут имхо всё прозрачно

Разве? Сравнивать строки по 10 символов и 10 млн. символов - совершенно подходы к решению :)

эхм, напомните, разве не Вы только что говорили о масштабировании?

и вот нифига подходы к решению не зависят об объёма данных :) скорее уж они зависят от объёма доступной памяти, от требуемого быстродействия, от средней длины ключа в конце концов и только потом, в самую распоследнюю очередь, возможно (!), от объёма текста

и да, не забывайте про условие задачи

Есть список строк, длиной от 5 до 50 символов

а то, мне кажется, Вы себе представляете строки длиной 12 млн. символов :)

и вот нифига подходы к решению не зависят об объёма данных :) скорее уж они зависят от объёма доступной памяти, от требуемого быстродействия, от средней длины ключа в конце концов и только потом, в самую распоследнюю очередь, возможно (!), от объёма текста

Я про длину строки и говорю, а не всего текста.

Есть список строк, длиной от 5 до 50 символов

а то, мне кажется, Вы себе представляете строки длиной 12 млн. символов :)

Тут думать даже не надо: строки добивать до 64 байт, сравнивать xmm-регистрами =) Две операции загрузки, одна сравнивания.

s/сравнивания/сравнения/

> а то, мне кажется, Вы себе представляете строки длиной 12 млн. символов :)

Тут думать даже не надо: строки добивать до 64 байт, сравнивать xmm-регистрами =) Две операции загрузки, одна сравнивания.

а что кстати, вполне приличный вариант :) только есть ньюанс, надо учитывать какая у ТС хост-система и есть ли там пресловутый xmm, а если есть то какая у него разрядность

и да, рискуя поразить КО в самое сердце, «нопоминаю» что 50 символов могут занимать от 50 до 200 байт

кстати, вот нашёл реализацию ternary search tree на питоне http://ifdown.net/2007/12/19/simple-applied-ternary-search-tree-in-python

а что кстати, вполне приличный вариант :) только есть ньюанс, надо учитывать какая у ТС хост-система и есть ли там пресловутый xmm, а если есть то какая у него разрядность

С работающим wine'ом-то? :) И mmx когда появился, лет 13 назад? :) У которого регистры как раз 64 бита.

и да, рискуя поразить КО в самое сердце, «нопоминаю» что 50 символов могут занимать от 50 до 200 байт

Не важно, для вариации cmp это всё равно блоб. Даже если 16 сравнений сделать (для килобайтной строки), то это всё равно будет быстрей вычисления хэша.

Но я бы не заморчивался, и сделал по-топорному :)

а что кстати, вполне приличный вариант :) только есть ньюанс, надо учитывать какая у ТС хост-система и есть ли там пресловутый xmm, а если есть то какая у него разрядность

С работающим wine'ом-то? :) И mmx когда появился, лет 13 назад? :) У которого регистры как раз 64 бита.

простите, но не везде mmx есть :) есть ведь ещё и risc процессоры и процессоры во всяких встроенных системах

и да и у amd64 оно вроде 128 бит, не?

простите, но не везде mmx есть :) есть ведь ещё и risc процессоры и процессоры во всяких встроенных системах

По поводу наличия mmx на современных и не очень x86oid'ах уже озвучивал (перефразирую: современный попсовый дистрибутив на машине уровня P133 уже и не запустится). По поводу работоспособности wine на не-x86oid'ах сомневаюсь. Это же не эмулятор типа qemu, а простой транслятор api.

и да и у amd64 оно вроде 128 бит, не?

У SSE2(+) регистры 128-битные, но на MMX это никак не влияет.

простите, но не везде mmx есть :) есть ведь ещё и risc процессоры и процессоры во всяких встроенных системах

По поводу наличия mmx на современных и не очень x86oid'ах

я намекаю на тот факт что никто не сказал что архитектура хоста x86 :)

я намекаю на тот факт что никто не сказал что архитектура хоста x86 :)

Интересно, на какой платформе нужна программа, работающая с файлами wine? :)

я намекаю на тот факт что никто не сказал что архитектура хоста x86 :)

Интересно, на какой платформе нужна программа, работающая с файлами wine? :)

эхм, да, чего-то я проморгал :)))

Насколько я понял, речь не про файлы wine, он лишь приведён в пример как содержащийся в поле exec у .desktop-файлов