Python-сообщество

Спасибо большое, погуглил по Вашему ответу, вроде понял про промах и попадание. И почему проц не работал “на всю катушку”.

А “used = set()” это собственно данные файла? Чет не могу въехать ни как в код.

Да медленный =) полтора часа файл перебирал…

Отредактировано (Дек. 30, 2010 10:39:07)

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

Спасибо за внимание.

Туда ли я попал? http://ru.wikipedia.org/wiki/Хеш-таблица

Я правильно понимаю, что для каждой строки вычисляется хеш как индекс и потом проверяется нет ли элементов с одинаковыми индексами? Т.е. строка - ключ, хеш от ключа - индекс.

Полтора часа против трех секунд… Я в шоке… Я не хочу просто взять код. Хочу понять как работает.

————-ADD————

файл из 2 000 000 строк (скопировал файл несколько раз) за секунду!!! Сча себя таким быдлокодером ощущаю, что хочется пальцы сломать.

————-ADD————

поправочка - в первый раз меньше чем за секунду пробежал (не туда посмотрел).

Отредактировано (Дек. 30, 2010 11:23:57)

Да. Хэш-таблицы могут быть устроены чуть по разному (в Питоне - Кнут, вариант D).
Главное - у них константное время доступа.

В результате мой вариант имеет линейную сложность (одна пробежка по файлу, хэш константный).

Ваш - квадратичный (цикл по строкам, внутри которого .count делает еще одну пробежку).

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

baragoz
Полтора часа против трех секунд…

Андрей Светлов

with open(outfile, 'w') as dst:

used = set()
for line in with open(filename, 'r'):
    used.add(line)
dst = open(outfile, 'w'):
dst.writelines(iter(line))

А где ваш порядок строк?

Андрей Светлов
А где ваш порядок строк?