Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

ведь всего-то 300 метров

Страницы: 1 2 >
tippa © (2010-06-19 10:21:00)
Подскажите пожалуйта.
Имеется файл размером 300 мегабайт, состоящий из 30 миллионов строк, при попытке его загрузки в StringList выскакивает ошибка, мол нехватает памяти. Оперативы 1 гигабайт. Это нормально?
Как можно провести сортировку строк в таком файле?

Плохиш (2010-07-20 20:53:00) [1]
а шо, аФФтар ещё здеся?

_Юрий (2010-07-20 20:49:00) [2]
В общем, сортированный THashedStringList с duplicates = dupIgnore и счетчиками в Objects
один проход.

Jeer (2010-07-20 14:53:00) [3]

> WWW (20.07.10 13:27) [31]
>
> Если 30 млн строк, то это одно, если же 30 млн слов, то
> это совсем другое. В русском языке впринципе не может быть
> 30 млн, слов, так что если повторяющиеся слова не нужны,
> то рекомендую поудалять повторяющиеся слова

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

WWW (2010-07-20 13:27:00) [4]
Если 30 млн строк, то это одно, если же 30 млн слов, то это совсем другое. В русском языке впринципе не может быть 30 млн, слов, так что если повторяющиеся слова не нужны, то рекомендую поудалять повторяющиеся слова

Rouse_ (2010-06-20 18:12:00) [5]
В моем алгоритме (ссылку на который привели) как раз в качестве хэша используется уникальный индекс слова в накопительном буффере. Т.е. сами слова добавляются в накопительный буффер и более не трогаются, сортируются только их индексы в TList-е

Sha (2010-06-20 12:07:00) [6]
При правильном использовании хеш-таблиц,
число коллизий для одного ключа, как правило, равно нулю.
Т.е. размер списка равен 1. Там ничего не надо сортировать.

Например, в задаче автора, достаточно выбрать размер таблицы
100K, если слова без различных словоформ.

Anatoly Podgoretsky (2010-06-20 11:30:00) [7]
> Sha (20.06.2010 11:07:27) [27]

Хеш список точно также надо сортировать

string --> List
string --> hash --> List

При несортированом списке аналогично

Sha (2010-06-20 11:07:00) [8]
> Anatoly Podgoretsky © (20.06.10 10:54) [26]

Да. Хоть TList, хоть array of, хоть связный.
Все равно придется вести массив указателей для быстрого поиска.

Хеш-таблица фактически разбивает этот массив
на несколько массивов меньшего размера (обычно разера 1)
и быстро определяет, какой из них надо использовать.

Anatoly Podgoretsky (2010-06-20 10:54:00) [9]
> Sha (20.06.2010 10:31:25) [25]

Список, типа TList?

Sha (2010-06-20 10:31:00) [10]
> Anatoly Podgoretsky © (19.06.10 20:25) [24]
> Слово в списке, само по себе является хешем,
> нет нужды тратить время на генерацию хеша

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

Anatoly Podgoretsky (2010-06-19 20:25:00) [11]
> RWolf (19.06.2010 19:50:22) [22]

Слово в списке, само по себе является хешем, нет нужды тратить время на
генерацию хеша.

tippa (2010-06-19 19:52:00) [12]
спасибо

RWolf (2010-06-19 19:50:00) [13]
[21]
самая затратная по времени операция — это как раз «есть ли слово в списке», поэтому контейнер для пар нужно выбрать с минимальным временем поиска. Для хэш-таблицы оно составляет О(1).

RWolf (2010-06-19 19:44:00) [14]

> tippa © (19.06.10 19:40) [20]

завести пустой список пар «строка-число» пока не прочитаны все слова из файла: прочитать слово если слово есть в списке - увеличить число, иначе добавить в список пару «слово - число 1»

tippa (2010-06-19 19:40:00) [15]
RWolf, будь хорошим человеком - объясни мне бестолковому в двух словах.

RWolf (2010-06-19 19:34:00) [16]
да тут дел на 5 минут, и ещё 5, чтобы прикрутить какой-нибудь прогресс-бар для наглядности, что там гуглить?

tippa (2010-06-19 19:28:00) [17]
Вот счас думаю найду готовую програмку. Фига с два. Нагуглил одну- единственную - Wordstat называется( http://dubinsky.ru/wordstat.htm), запехнул в неё свой файлик - програмка подумала и вылетела. Больше ничего подобного не нашел. Ковыряемся дальше)

Anatoly Podgoretsky (2010-06-19 19:15:00) [18]
> tippa (19.06.2010 18:57:12) [12]

Даже если и влезет, то работать будет много часов, может дней.

Anatoly Podgoretsky (2010-06-19 19:14:00) [19]
> [true]trix (19.06.2010 18:46:11) [11]

Даже при линейной зависимости как минимум в 100 раз больше, минимум 5 минут,
но вряд ли зависимость линейная.

Anatoly Podgoretsky (2010-06-19 19:12:00) [20]
> RWolf (19.06.2010 18:28:10) [10]

Ну тогда немного легче, хоть и некрасиво с его стороны, но все равно я бы
загнал БД и сразу бы получил ответ по каждому слову.

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »