Автор Тема: Разобраться с 100000000 строк  (Прочитано 15602 раз)

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #15 : Апрель 04, 2012, 09:25:52 pm »
Задача не полна без её "приземления". Например может оказаться что у нас памяти больше нет ВООБЩЕ (ну. то есть памяти есть O(1)). Тогда нужно трансформировать данные на месте.

Либо памяти у нас завались и надо сделать как можно быстрее.

Либо у нас память бывает разная - очень быстрая, но мало, средне средней и завались медленной. Все данные целиком единым куском влазят только в медленную. Оптимизируем по скрости.

Ну и так далее. Кроме всего прочего, разные операции могут еще по разному стоить (сравнение - одна стоимость, копирование - совсем уже другая).

Также операции (некоторые) в некоторых случаях могут векторизироваться.

Ну и т.д. и т.п.

Поэтому, на собеседовании, когда я человеку коварно даю алгоритмическую задачку и НЕ уточняю вешеперечисленные особенности, я обычно ожидаю либо увидеть самое простое (и потому поддерживаемое) решение, либо услушать множество уточняющих вопросов (на которые я обычно говорю - после узнаешь, ты напиши для начала как-нибудь).
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #16 : Апрель 04, 2012, 09:27:51 pm »
Итеративное добавление в АВЛ дерево займет O(n*lon(n)) времени. Быстрее сделать сортировку.

Вообще по каким критериям оптимизируем?
Не делал (по этому и интересуюсь) , рекурсивное log2 (n)+20-40%. вообще задача забавная... а контора.. --mmorpg клепатели  :) , обычное добавление (в простое BSD) vs рекурсивным дает 10-15% выигрыша (память не считаем...). По всем, основной - время -Предлагаю просто оценить задачу (возможное решение) без реализации  :)

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #17 : Апрель 04, 2012, 09:31:46 pm »
BST - не BSD, конечно.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #18 : Апрель 04, 2012, 09:33:03 pm »
А если тупо хэш? (коль уж у нас памяти не меряно)
Будет, как я понимаю, O(n)
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #19 : Апрель 04, 2012, 09:41:18 pm »
А если тупо хэш? (коль уж у нас памяти не меряно)
Будет, как я понимаю, O(n)
А что есть идеи как подобрать хэш функцию дающую открытую адресацию по такого рода набору данных?

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #20 : Апрель 04, 2012, 09:48:25 pm »
было бы конечно круто...  :) ведь набор данных известен... но я такой методы не знаю   :(   :)

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Разобраться с 100000000 строк
« Ответ #21 : Апрель 04, 2012, 10:25:15 pm »
А что есть идеи как подобрать хэш функцию ... ?
Это вообще не проблема. Эффективность произвольной "вменяемой" хэшфункции на большой выборке очень слабо отличается от теоретического предела 0.63 = 1 - 1/E. Поэтому можно брать самую простую, например такую:

uint h = 0;
int i = 0;
while (i < length)
{
   h = h * factor + s[i++];
}

uint factor - число взаимно простое с размером таблицы и желательно большее чем максимальное значение кода какой-либо буквы, например 74653.

---------------------

Конечно надо использовать хэширование. А оптимизировать тут видимо надо чтение этого файла и запись другого файла с результатом. Обычные жёсткие диски работают со скоростью 60-70 Мб/сек. То есть для 200 Мб файла три секунды уйдёт только лишь на чтение, затем три секунды уйдёт только лишь на запись результата. Файл лучше отобразить в память или записать в непрерывный массив букв размером эти самые 200 Мб, то есть отдельные объекты-строки не создавать ибо достаточно будет запомнить (в другом массиве) начальные индексы строк (кстати, длины строк тоже не обязательно запоминать ибо их можно вычислить по разности соседних индексов).

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Разобраться с 100000000 строк
« Ответ #22 : Апрель 04, 2012, 10:30:10 pm »
Ежели будет использовано не отображение файла в память, а чтение в массив букв, то повторные строки в него, конечно, писать не нужно.

Romiras

  • Sr. Member
  • ****
  • Сообщений: 264
    • Просмотр профиля
    • Romiras Dev Lab
Re: Разобраться с 100000000 строк
« Ответ #23 : Апрель 04, 2012, 11:01:37 pm »
Наверно, во время собеседования немаловажно узнать ход рассуждений. Узнать почему выбран тот или иной способ решения, между какими другими вариантами были колебания.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #24 : Апрель 04, 2012, 11:02:50 pm »
Наверно, во время собеседования немаловажно узнать ход рассуждений. Узнать почему выбран тот или иной способ решения, между какими другими вариантами были колебания.
Угу. Потому я и описал примерный ход беседы когда я провожу собеседование.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #25 : Апрель 05, 2012, 04:13:30 am »
А что есть идеи как подобрать хэш функцию ... ?
Это вообще не проблема. Эффективность произвольной "вменяемой" хэшфункции на большой выборке очень слабо отличается от теоретического предела 0.63 = 1 - 1/E. Поэтому можно брать самую простую, например такую:

uint h = 0;
int i = 0;
while (i < length)
{
   h = h * factor + s[i++];
}

uint factor - число взаимно простое с размером таблицы и желательно большее чем максимальное значение кода какой-либо буквы, например 74653.

---------------------

Конечно надо использовать хэширование. А оптимизировать тут видимо надо чтение этого файла и запись другого файла с результатом. Обычные жёсткие диски работают со скоростью 60-70 Мб/сек. То есть для 200 Мб файла три секунды уйдёт только лишь на чтение, затем три секунды уйдёт только лишь на запись результата. Файл лучше отобразить в память или записать в непрерывный массив букв размером эти самые 200 Мб, то есть отдельные объекты-строки не создавать ибо достаточно будет запомнить (в другом массиве) начальные индексы строк (кстати, длины строк тоже не обязательно запоминать ибо их можно вычислить по разности соседних индексов).
1.  Я говорил не про хэш функцию ВООБЩЕ, а про гарантированно дающую открытую адресацию (взаимооднозначное отображение заданного множества ключей на множество значений)
2. А вот со вторым -  ОК (все по делу)  :)
« Последнее редактирование: Апрель 05, 2012, 04:17:21 am от DIzer »

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #26 : Апрель 05, 2012, 04:30:00 am »
Наверно, во время собеседования немаловажно узнать ход рассуждений. Узнать почему выбран тот или иной способ решения, между какими другими вариантами были колебания.
Угу. Потому я и описал примерный ход беседы когда я провожу собеседование.
Да, с учетом того что задача дается "факультативно" - потенциальный работодатель вполне может (и должен  ИМХО) рассчитывать на "взвешенное" решение.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #27 : Апрель 05, 2012, 04:38:53 am »
Разобрать файл, закачать в MSAccess. Потом можно резвиться как угодно - сортировать вперед-назад, считать количество уникальных, количество повторений и пр.
Если Access не подходит по религиозным соображениям - заменить.

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #28 : Апрель 05, 2012, 04:46:25 am »
 ;) Как вариант пойдет ( как использование сторонней  реализации работы с  одним из  видов B- деревьев) - но вот помню еще лет 10 назад он хреновато работал на данных такого обьема...

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #29 : Апрель 05, 2012, 11:11:43 am »
Но вопрос, зачем? Сергей довольно детально изложил нормальную  схему действий
1. Строим хэш функцию отображающую строку на 0..9999999 (с коллизиями)
2. Создаем массив указателей на подходящую структуру
3. Для каждой строки вычисляем хэш, пытаемся запихнуть в массив если ячейка пуста, то создаем  структуру (запихиваем строку, количество повторений) если занята - сравниваем хранящиеся строки  -если они равны увеличиваем счетчик иначе ищем свободную ячейку создаем структуру в ней...(т.е. разрешаем коллизии)... ну а после этого неблагодарного дела пробегаемся по массиву еще раз и формируем выходной файл...
Остальные оптимизации... дело вкуса.