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

Собственно, очень интересуют варианты подхода к решению.

1. Старая добрая игра “Балда”. Надо моментально определять, существует ли такое слово в словаре или нет.

2. Два файла-слепка файловой системы в разное время (допустим, a и b), каждый в plain text содержит список абсолютных путей до каждого файла. В беспорядке. Задача - найти файлы, которые удалились и которые добавились за это время. Файлы очень большие, ресурсов очень мало.

Я так понимаю, что оптимальным решением для первой задачи может быть Trie. То есть мы по мере набора букв обходим дерево и проверяем на успех. Вопрос в таком случае касается только хранения - в каком виде хранить эту префиксную структуру? Например, в MySQL?

Со второй не все так просто. Хотя, в принципе, Trie тоже подходит. Но, возможно, существует какое-то более эффективное решение… Хэширование тоже не очень подходит, ибо в память все равно не влезет.

Есть что-то похожее в блоге Гвидо: http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html , я только начал это дело разбирать.

В общем, кто что думает по данной теме?

Отредактировано (Фев. 23, 2011 00:24:12)

сколько фалов ориентировочно?

Enchantner
Собственно, очень интересуют варианты подхода к решению.

1. Старая добрая игра “Балда”. Надо моментально определять, существует ли такое слово в словаре или нет.

2. Два файла-слепка файловой системы в разное время (допустим, a и b), каждый в plain text содержит список абсолютных путей до каждого файла. В беспорядке. Задача - найти файлы, которые удалились и которые добавились за это время. Файлы очень большие, ресурсов очень мало.

Я так понимаю, что оптимальным решением для первой задачи может быть Trie. То есть мы по мере набора букв обходим дерево и проверяем на успех. Вопрос в таком случае касается только хранения - в каком виде хранить эту префиксную структуру? Например, в MySQL?

Со второй не все так просто. Хотя, в принципе, Trie тоже подходит. Но, возможно, существует какое-то более эффективное решение… Хэширование тоже не очень подходит, ибо в память все равно не влезет.

Есть что-то похожее в блоге Гвидо: http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html , я только начал это дело разбирать.

В общем, кто что думает по данной теме?

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

Пиши - так и так, то то и то то

В mysql возможно хранить любое дерево. В т.ч. и твое.

Да, например в mysql ! Да где угодно. Распарсить их нужно и разложить. Твои деревья.

А потом сесть и подумать. Как, бля, лучше будет.

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

Стиль оформления твоего ответа, leechuck, мне кое кого напомнил… Только у того Аццкого чувака мата было меньше, хотя может он просто подрос?
А вообще, это твое третье сообщение на форуме, а ты уже пальцем тыкаешь в то, сколько многоточий использовать… Не хорошо…

Enchantner
1. Старая добрая игра “Балда”. Надо моментально определять, существует ли такое слово в словаре или нет.

Этот словарь в set влезет? Если да, то всё просто.

Enchantner
2. Два файла-слепка файловой системы в разное время (допустим, a и b), каждый в plain text содержит список абсолютных путей до каждого файла. В беспорядке. Задача - найти файлы, которые удалились и которые добавились за это время. Файлы очень большие, ресурсов очень мало.

Поищи по форуму: не так давно очень похожая задача обсуждалась. Притом довольно долго и, вроде, успешно.

як говориця, ты чи пидрос :)

ZZZ
Этот словарь в set влезет? Если да, то всё просто.

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

P.S. И да, зачем в “Центр помощи” перенесли? Это не задачки на контрольной, это мое личное исследование по алгоритмам такого типа :)

Старая добрая балда, решается старой доброй дихотомией.
Файл с отсортированными словами, время поиска логарифмическое. Ты ничего не написал про вставку, нужна ли она? Если нет, то отсортированный файл хороший выбор. Правда, для того чтобы прыгать по строчкам, придется взять строку фиксированной длины…

Фишка с набором букв - не очень, потому что буквы можно набирать например так: “првет”, а потом вбить недостающую букву в нужное место “прИвет”.

Во втором случае есть два дерева, и надо их сравнить. Алгоритмы сравнения деревьев есть. Ну или можно заставить бд сравнить их через какой-нибудь джоин :)


ЗЫ В гугл взяли? Или готовишься? :)

Отредактировано (Фев. 23, 2011 12:52:41)

Zubchick
Фишка с набором букв - не очень, потому что буквы можно набирать например так: “првет”, а потом вбить недостающую букву в нужное место “прИвет”.

Нельзя, в балде выбор букв идет строго по порядку в слове :) А решать дихотомией - ты имеешь в виду просто двоичный поиск по отсортированному массиву слов? И как это сделать в базе?

Zubchick
Файл с отсортированными словами, время поиска логарифмическое. Ты ничего не написал про вставку, нужна ли она? Если нет, то отсортированный файл хороший выбор. Правда, для того чтобы прыгать по строчкам, придется взять строку фиксированной длины…

В том-то и фишка, что не отсортированными, а если файлы большие - то сортировка займет очень долгое время…

P.S. Готовлюсь, да, а задачка, кстати, не из гугла, а от Parallels :)