| Вопрос: Рус-яп словарь. Что выбрать для БД? | Добавлено: 23.06.05 10:43 |
Автор вопроса:  Ruslan_x
|
| Ответы | Всего ответов: 52 |
|
Номер ответа: 16 Автор ответа:  Morpheus Вопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #16 | Добавлено: 26.06.05 17:53 |
|
абрикос - 0030
арбуз - 0045 ... яблоко - 8794 А вот тут точно INI файл нужен: [Index] Арбуз=0045.... только вот на счёт русских букв не уверен |
||
|
Номер ответа: 17 Автор ответа: ПавелАдминистратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | | #17 | Добавлено: 26.06.05 18:07 |
|
Используйте класс HashTable, он полностью подходит под вашу задачу. А если очень хочется использовать бинарный поиск, то используйте для хранения ключей класс ArrayList: его методы Sort и BinarySearch позволят отсортировать элементы и провести бинарный поиск. |
||
|
Номер ответа: 18 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #18 | Добавлено: 26.06.05 18:54 |
|
А для чего все эти навороты: хэш-таблицы, методы BinarySearch и Sort какого-то левого класса?
Если статей в словаре 500000, то просто держать в файлах указателей сами слова и соответствующие номера статей, разбитые по алфавиту: одна буква (первая) - один файл. Так снижается требования к памяти (грубо говоря, в 33 раза меньше). Допустим абрикос: взяли первую букву - а, открыли файл "a.txt", бинарным поиском нашли слово и открыли статью, соответствующего номера. Какие тут могут быть проблемы? Чаще всего в русском языке встречается буква "о", ~20%, значит максимум в одном файле будет порядка 100000 записей -> элементарным поиском это всего 16 сравнений, и запись найдена. Добавление записей производить сразу в нужное место - в алфавитном порядке, и никаких Sort не нужно будет. При добавлении пользоваться тем же методом, что и при поиске строки. Изначально всё будет сортировано. А хэш - это типа навороты для верблюда 
Сделать нормальную хэш-функцию, без коллизий, сложно, да и вряд ли с ней будет работать быстрее, чем простое и банальное сравнение десятка строк. Можно несколько "заголовочных" файлов объединить в один, если пугает 33 файла Например а - е, ж - м, н - о, п - с, т - я. Пять файлов - немного.
Имхо, никакая суперпупер база и никакой суперпупер класс не сработают быстрее обычного текстового файла, обслуживаемого простым и эффективным алгоритмом. И памяти жрать меньше будет. |
||
|
Номер ответа: 19 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #19 | Добавлено: 26.06.05 19:01 |
| Что касается памяти, то просто посчитать, приняв среднюю длину строки за 10 букв + 10 на номер статьи и разные побочные дела, получается если пять файлов то грубо говоря, 20 * 100000 = 2 Мб | ||
|
Номер ответа: 20 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #20 | Добавлено: 26.06.05 21:36 |
| Представь себе сервер, обслуживающий 100 клиентов в секунду, там такая детская схема не прокатит. Хэш-функцию можно взять готовую, причем т.к. длина значения хэш-функции фиксирована, сравнение будет проходить быстрее. | ||
|
Номер ответа: 21 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #21 | Добавлено: 26.06.05 22:21 |
|
Можно представить и сервер, обслуживающий 100 миллион клиентов в десятую долю секунды, вопрос только в том, пишет ли Ruslan_x такого рода программу или нет И навороченный вариант далеко не всегда самый лучший. Конкретная ситуация диктует выбор средств.
Может попробуешь сделать поиск среди 500000 записей индекса статьи быстрее, чем сделаю я? Хэш+скулы+сервер+ещё что угодно против обычного текстового файла? |
||
|
Номер ответа: 22 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #22 | Добавлено: 27.06.05 09:40 |
| Ты файл с первой буквой будешь дольше открывать, чем я проделаю все операции: и хэширование, и бинарный поиск, и нахождение статьи | ||
|
Номер ответа: 23 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #23 | Добавлено: 27.06.05 11:34 |
| Ты запускать свой сервер будешь дольше, чем я найду нужный файл и нужную строку в файле и покажу соответствующую статью | ||
|
Номер ответа: 24 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #24 | Добавлено: 27.06.05 16:58 |
| Необоснованное утверждение. Предполагается, что программа уже запущена | ||
|
Номер ответа: 25 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #25 | Добавлено: 27.06.05 17:58 |
| Предпологается, что серверу тут не место. Читай ответ номер пять. | ||
|
Номер ответа: 26 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #26 | Добавлено: 27.06.05 17:59 |
|
Заодно можешь вспомнить ответ номер шесть
|
||
|
Номер ответа: 27 Автор ответа: ПавелАдминистратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | | #27 | Добавлено: 27.06.05 18:09 |
| А кто вообще говорит о базах данных? Упомянутые Sharp'ом таблицы можно без проблем сохранить в файл в некоем виде: XML, бинарная сериализация, или какой-то свой формат... Отсортировать предварительно, перед установкой/запуском программы. При запуске программы грузить в память. Тогда все будет работать достаточно быстро, если не считать большого объема занимаемой оперативной памяти... | ||
|
Номер ответа: 28 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #28 | Добавлено: 27.06.05 18:58 |
|
Павел
Ну дык а я о чём говорю С той лишь разницей, что не упомянутые таблицы хранить, а просто саму строку, благо они короткие. И не морочиться с хэшами/таблицами.
А для снижения нагрузки на память разбить файл на несколько, чтобы не держать сразу всё в памяти. Более того, вообще не грузить его в память ReadFile'ом, а сделать MapView. Тогда можно один файл спокойно любого объёма. Не думаю, что надо выдавать тысячи номеров статей в секунду, чтобы держать всё в памяти
|
||
|
Номер ответа: 29 Автор ответа: Ruslan_x Вопросов: 7 Ответов: 41 |
Профиль | | #29 | Добавлено: 27.06.05 19:55 |
|
Уважаемые участники форума, огромное аригато из далекой Японии за ваши ответы.
Чувствую, что нужно прояснить несколько моментов. Сделай индексы так: две таблицы типа хэш-статья (для русского и японского), отсортируй по хэшам, затем binary search (aka b-tree) хэшируй запрошенное слово и сравнивай полученный хэш с серединой списка хэшей. Если больше, рассматривай вторую половину, меньше - первую, угадал - радуйся и так, пока не найдешь нужную статью. Нашел - выводишь. А 50-60 метров очень жирно. Пусть 16 байт на хэш, 4 байта на ид статьи, 500 тыс. записей, две таблицы, максимум 20 метров.
Момент 1. ------------------ При тестировании я так и делал. Использовал NameValueCollection для хранения индекса. Однако, в конечном итоге не хотелось бы хранить индекс в памяти. Потому что таблицы нужно будет не две, а три. Третья таблица - это поиск по японскому чтению, т.е. уже получается 30 Мб. Не хочется занимать оперативку и замедлять загрузку программы. Таким образом остается одно - хранить индекс на диске. ------------------- Используйте класс HashTable, он полностью подходит под вашу задачу.
Момент 2. ------------------- Мне кажется, что HashTable в виде индекса для этого проекта не совсем подходит. Потому что ключи не являются уникальными. Другими словами, на слово "абрикос" может быть не одна статья, а две, три или вообще десять. Насколько мне известно, в VB.NET единственный вариант хэш-таблицы, позволяющий иметь несколько одинаковых ключей - это NameValueCollection. А если очень хочется использовать бинарный поиск, то используйте для хранения ключей класс ArrayList: его методы Sort и BinarySearch позволят отсортировать элементы и провести бинарный поиск.
Проблема не в том, что я не могу сделать поиск. Поиск я могу сделать - если индекс находится в памяти в виде того же ArrayList. Проблема в том, как сделать быстрый поиск, если индекс хранится в виде файла на диске. И загружать весь индекс в память я не хочу. Если статей в словаре 500000, то просто держать в файлах указателей сами слова и соответствующие номера статей, разбитые по алфавиту: одна буква (первая) - один файл. Так снижается требования к памяти (грубо говоря, в 33 раза меньше).
To HOOLIGAN: Очень интересная идея, но все же не хотелось бы плодить кучу файлов. Даже если их будет 5-6, то для это ж для каждого из 3-х индексов... Допустим абрикос: взяли первую букву - а, открыли файл "a.txt", бинарным поиском нашли слово и открыли статью, соответствующего номера.
"Открыли файл" - это значит полностью загрузили его в память? Если загружать файлы в память, то можно просто тот же индекс в виде NameValueCollection десериализовать с диска. Заковыка в том, что не хочется ничего лишнего в оперативку грузить, хочется все сделать с помощью десятка-другого обращений к файлам на диске. Хотя по большому счету, меня волнуют вовсе не эти технические детали, а основные требования: - чтобы программа быстро грузилась - чтобы быстро находила нужную запись - чтобы не занимала много места в оперативке Sharp:
Ты файл с первой буквой будешь дольше открывать, чем я проделаю все операции: и хэширование, и бинарный поиск, и нахождение статьи ----------- HOOLIGAN: Ты запускать свой сервер будешь дольше, чем я найду нужный файл и нужную строку в файле и покажу соответствующую статью Похоже, это один из тех случаев, когда в споре рождается истина.
Честно говоря, очень хотелось бы протестировать оба подхода, чтобы докопаться, чья точка зрения вернее. Но это, к сожалению, нереально. Наверняка, каждый подход имеет свои плюсы и минусы. Мне так кажется, что если вести речь о сервере, на котором крутится программа, то подход Sharp, возможно, лучше. Но для самостоятельной программы мне больше по душе подход HOOLIGAN. Сказать по правде, после того, как я сделаю программу, то хотелось бы также сделать доступ к словарной базе через Web-сайт. Нагрузка там вряд ли будет большой. Я так думаю, что максимум где-то 1-2 клиента в секунду. Было бы неплохо, конечно, использовать один и тот же механизм и на сайте и в программе. Но пока что главый приоритет - это отдельная программа. ********************** Пока что я пришел к вот к какому решению, которое мне кажется далеко не идеальным. Буду признателен за замечания и критику. Итак, в отдельном файле хранятся записи. Назовем его "  IC.DAT".
Для простоты возьмем только один индекс по русским словам. Вот он: -------------- абрикос - 0030 арбуз - 0045 ... яблоко - 8794 --------------- Цифра - это местоположение записи в основном файле " IC.DAT".
Как я уже говорил выше, одному ключу-слову может соответствовать не одна, а несколько записей. Другими словами: --------------- абрикос - 0030 арбуз - 0045 арбуз - 0048 арбуз - 0053 арбуз - 0129 .... или абрикос - 0030 арбуз - 0045,0048,0053,0129 ... --------------- В качестве индексного файла " IC.IDX" я хочу использовать Random Access файл, который предварительно отсортирован по русскому слову.
В предыдущем посте я спрашивал, как конкретно реализовать Binary search. Долгие поиски в инете меня привели к решению. Привожу его здесь - может кому пригодится. Думаю, для большинства тут нет ничего нового, но для нас, начинающих, такие куски кода очень нужны. Вообще-то это binary search для массива, а не для файла, но переделать его не сложно. ++++++++++++++++++++++++++++++ Sample List: 1. Alex 2. Dave 3. Dan 4. Dylan 5. Jason 6. Kyle 7. Matt 8. Saroja To code a user-defined function in VB that returned the index of a name in an array of names, we could write: private function findName(byref names() as string, byval seekName as string) as integer dim found as boolean dim lowIndex as integer dim highIndex as integer dim middleIndex as integer found = false lowIndex = 0 highIndex = Ubound(names) middleIndex = int((highIndex + lowIndex)/2) do while (NOT found and lowIndex < highIndex) if seekName = names(middleIndex) then found = true elseif seekName > names(middleIndex) then lowIndex = middleIndex + 1 middleIndex = int((highIndex + lowIndex)/2) else highIndex = middleIndex - 1 middleIndex = int((highIndex + lowIndex)/2) end if loop if found = true then findName = middleIndex else findName = -1 end if end sub ++++++++++++++++++++++++++++++ Проблема с Random Access файлом в том, что все записи должны быть одинаковой длинны. Скажем, 20 символов на слово и 4 - на смещение. Т.е. мы не сможем сделать: ------------- арбуз - 0045,0048,0053,0129 ------------- Таким образом наш арбуз будет многократно повторяться: ------------- арбуз - 0045 арбуз - 0048 арбуз - 0053 арбуз - 0129 ------------- Вот это "повторение арбуза" мне не нравится. И вот почему. С помощью binary search я найду первый арбуз в списке. А как мне найти остальные, которые могут быть выше или ниже его? Нет, конечно, можно написать дополнительный код, который это все сделает, но это - дополнительные тормоза. Единственное, что мне пришло на ум - это ввести дополнительный индекс. В виде Binary Access файла " IC.ID2".
И в основном индексе " IC.IDX" указывать на то место в этом дополнительном индексе "IC.ID2", где хранятся смещения основного файла "IC.DAT".
Таким образом наши несколько арбузов становится одним: ------------- абрикос - 0204 арбуз - 0218 банан - 0267 ------------- Смещение арбуза "0218" показывает на то место в " IC.ID2", где хранятся все его смещения в основном файле "0045,0048,0053,0129".
Думаю, нужно давать медаль тем, кто дочитал до этого места.
Короче, этот подход плодит два индексных файла вместо одного и это, похоже, единственный недостаток, который мне бросается в глаза. Как это все сделать лучше - я не знаю. Буду признателен за любые комментарии, замечания и критику. ---------------- Вопросы к HOOLIGAN: Ну дык а я о чём говорю
С той лишь разницей, что не упомянутые таблицы хранить, а просто саму строку, благо они короткие. И не морочиться с хэшами/таблицами."...а просто саму строку" Какую "строку" вы имеете в виду? 1) Саму запись из словаря типа "вкусный арбуз - OISHII SUIKA" 2) Индексную информацию "арбуз - 0045" Более того, вообще не грузить его в память ReadFile'ом, а сделать MapViewю
Не могли бы вы в двух словах объяснить про MapView? |
||
|
Номер ответа: 30 Автор ответа: HOOLIGANВопросов: 0 Ответов: 1066 |
Профиль | | #30 | Добавлено: 28.06.05 00:44 |
|
Начнем с начала, нет, лучше с конца
На конце у нас MapView: Это такой способ получения информации из файла, при котором файл целиком не грузится в оперативную память, только одна запись, которую считали в данный момент. Плюс - не надо памяти для открытого файла, каких бы он размеров не был. Обычно чем больше файл, тем эффективней MapViewOfFile и менее эффективен способ открытия через ReadFile. Минус MapViewOfFile - скорость ограничена вращением винта. Минус ReadFile'а - нужна память. Поэтому можно посоветовать такую схему: Если у тебя несколько индексов, описывающих статьи про арбуз по такому принципу: а -> арбуз -> красный -> сладкий -> 00001
незрелый -> 00002 сочный -> 00003 круглый -> зеленый -> 00004 полосатый -> 00005 с хвостиком -> 00006 абрикос -> оранжевый -> и т.д. б -> банан -> барабан -> и т.д. баран -> то лучше всего держать в самой быстрой части, т.е. считанной в память, только те индексы, которые старшие в схеме:<а-я> + <арбуз-яблоко>. Чтобы можно было быстро отсечь максимум ненужного. Если условно принять, что буквы равновероятно встечаются в алфавите, то взяв индекс <а>, отсекли от зоны поиска 97% объёма. Если у тебя всего миллион статей, то уже после первого индекса осталось всего 30 000. Но и эта цифра пусть не пугает, т.к. индексов, следующих за головными, не так уж и много: Если 30 000 статей на одну букву <а>, и каждое слово может иметь к примеру три статьи, то 10 000 слов для одной буквы. Это уже совсем по-детски. И так далее. Насколько позволит память, желательно побольше индексов старшего ранга держать в оперативе. Если держишь всего один индекс - головной, то оперативы нужно всего 33 строки, указывающих на 33 файла со списками слов. Т.е. 33 строки вида "a<a.txt>" - "я<я.txt>" Или всего 264 байта. Это вся оперативная память, что тебе нужна. И не надо пугаться 33 файлов. Наоборот, это твой козырь в погоне за скоростью - отсечь от зоны поиска как можно больше файлов. Если файл один - выбора нет - придется рыскать по всему файлу одним объёмом, если файлов 5 - будешь искать только в 20% общего объёма. Если 33 - в 3%. В общем схема такая: Один файл с 33 строками, зачитал его в память и держишь, чтобы не вырвался и не убежал. На запрос <арбуз красный сладкий> реагируешь так: получаешь первую букву "а", и находишь среди 33 строк такую, которая начинается с этой буквы. Открываешь файл, соответствующий этой букве. В открытом файле ищешь строки начинающиеся на "арбуз", их в нашем случае 6. 50 байт в среднем на строку хватит с запасом. Если для каждого слова взять по 6 определений, то 10000х6х50= 3 Мб на файл для одной буквы. Или 100 Мб места на винте под 33 файла. Думаю, что в твоём случае ни миллиона статей, ни по 6 статей на каждое слово не будет, поэтому можно принять это как максимальное значение, которого тебе хватит на все случаи и с запасом. Найдя в файле строку "арбуз красный сладкий 0001", ты имеешь номер статьи - 00001. Дальше делай с ним что хочешь, статья найдена. Имеется один головной файл размером 264 байта, 33 файла по 3 Мб максимум и огромный файл с твоими собственно конечными статьями (или несколько поменьше, непринципиально). Причём, вся эта масса не грузится в память, а спокойно валяется на винте. Сколько нужно времени на то, чтобы найти конкретную статью? Первый файл - 33 строки - максимум 6 сравнений строк (2^6>33) Второй файл - 10000 строк - 14 сравнений (2^14>10000). Время на открытие 2 файла размером 3 Мб - миллисекунды. Даже ReadFile'ом. Время на открытие последнего огромного файла со статьями - открывать при помощи MapViewOfFile, не читая в памяти - миллисекунды. А номер статьи 00001 пусть будет смещением от начала файла, на котором начинается твоя конкретная статья. Вызов одной апи SetFilePointer сразу установит указатель чтения на нужный адрес в файле. Зачитал статью с этого адреса и всё. Много ли времени надо, чтобы сравнить 20 строк? Хватит ли на это одной секунды? Могу сказать, что за 5 секунд можно не просто сравнить, а считать в память ReadFile'ом, отсортировать и сохранить в сортированном виде на винт файл размером 50 Мб из 200 000 строк. Не особо напрягаясь. А количество сравнений строк, и перестановок, которое при этом производится, измеряется многими миллионами. Думаю за 1 секунду можно найти статью. Главное - это не использование какого-нибудь ультрамодного и разрекламированного средства типа .net или скулосервера. Главное чётко представлять себе организацию данных, которые предстоит обрабатывать. И тогда простейший алгоритм будет работать быстрее любого другого, навороченного и не заточенного под конкретную задачу. Теперь о шести арбузах: нечего их бояться Записи будут добавляться по одной, поэтому при добавлении производишь точно такой же поиск, как при нахождении статьи, и найдя соседнюю пару строк, одна из которых меньше (по алфавиту), а другая больше, чем добавляемая, впихиваешь добавляемую между ними. Добавление не будет происходить ежесекундно, тут тем более некритична скорость. И твои данные будут автоматом в сортированном порядке, позволяющем вести обычный бинарный поиск, как самый эффективный в данном случае.
Последовательность маппирования файла это вызов следующих апи: CreateFile->CreateFileMapping->MapViewOfFile. В msdn всё это расписывается, наверняка и на vb найдёшь кучу примеров как использовать. Приведенная схема весьма проста, если есть желание, можно её усложнить, чтобы оптимизировать работу программы. И везде, где есть смысл, используй указатели как смещение от начала файлов, в котором предстоит искать. Те части, на которые ссылка идёт не абсолютная (как смещение), а просто как на имя файла, где искать, должны быть сортированы. Например если ищем арбуз, то в головном файле нет указателя на строку, содержащую арбуз, есть только имя файла. Поэтому, чтобы к этому файлу можно было применить бинарный поиск, этот файл должен быть сортирован, что достигается либо сразу добавлением записи в положенное ему по алфавиту место, либо отдельной сортировкой файла после добавления каждой новой строки. Первый вариант намного проще. Какую "строку" вы имеете в виду? 1) Саму запись из словаря типа "вкусный арбуз - OISHII SUIKA" 2) Индексную информацию "арбуз - 0045" Вторую строку. По-моему, я написал ещё больше, интересно, дочитает кто-нибудь до конца или нет )
|
||