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

DIzer

  • Гость
Разобраться с 100000000 строк
« : Апрель 04, 2012, 06:28:39 pm »
Есть топик находящийся в файле возможно с повторениями -вывести уникальные строки и количество их повториений- мой выбор АВЛ -дерево -кто может подсказать лучшее решение?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Разобраться с 100000000 строк
« Ответ #1 : Апрель 04, 2012, 08:04:54 pm »
Тупо отсортировать файл.  ;)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #3 : Апрель 04, 2012, 08:22:00 pm »
Тупо отсортировать файл.  ;)
А чем это лучше моего  предложения (кроме тупости, конечно)?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Разобраться с 100000000 строк
« Ответ #4 : Апрель 04, 2012, 08:24:08 pm »
Тупость важный параметр! :D
Ну а кроме... меньшим расходом оперативы. Сколько файл гигов то?

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #5 : Апрель 04, 2012, 08:27:36 pm »
Тупость важный параметр! :D
Ну а кроме... меньшим расходом оперативы. Сколько файл гигов то?
НУ пусть в среднем строка  -20 байт...

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Разобраться с 100000000 строк
« Ответ #6 : Апрель 04, 2012, 08:33:48 pm »
Ну вот 2 гига... У меня например никогда столько свободной памяти нет...

Я конечно не знаю сколько юниксовая утилита памяти жрет (по ссылке, что я приводил), но можно сортировкой слиянием сделать  :)

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #7 : Апрель 04, 2012, 08:40:14 pm »
Ох ты -еть...  :)  я лишний нолик приписал, однако.... в файле 10 миллионов строк то есть около 200мб

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Разобраться с 100000000 строк
« Ответ #8 : Апрель 04, 2012, 08:45:23 pm »
О как! :o

Ну тогда номенклатура алгоритмов ни чем не ограничена  :)

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

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #9 : Апрель 04, 2012, 08:47:44 pm »
Шо значить не ограничена... я же просил ЛУЧШЕЕ решение, ну и с обоснованием (так сказать защита от тупости)  ;D что бы не было пузырька в самой тупой  ипостаси...(2 йной for)
« Последнее редактирование: Апрель 04, 2012, 08:50:30 pm от DIzer »

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #10 : Апрель 04, 2012, 08:52:56 pm »
Да , кто нибудь делал итеративное добавление в  АВЛ дерево?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Разобраться с 100000000 строк
« Ответ #11 : Апрель 04, 2012, 08:56:26 pm »
Шо значить не ограничена... я же просил ЛУЧШЕЕ решение, ну и с обоснованием (так сказать защита от тупости)  ;D что бы не было пузырька в самой тупой  ипостаси...(2 йной for)
Задача практическая или образовательная?
Если практическая, то юникс утилита - это готовое решение. (там точно не пузырек :))

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #12 : Апрель 04, 2012, 09:09:14 pm »
 :) Трудно сказать (кому как)... это одна из 2 "конкурсных" задач для трудоустройства в одну из контор (обьявление я увидел рядом с деканатом) -  по идее, считаю , что такого уровня задачи студенты 1 курса должны брать (ну процентов 10 точно, при желании, конечно)... 

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Разобраться с 100000000 строк
« Ответ #13 : Апрель 04, 2012, 09:19:22 pm »
Странная задача для трудоустройства. А что там за сфера деятельности у работодателя?
Сдается мне, что в этом случае правильность алгоритма зависит от тараканов интервьювера  ;)

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #14 : Апрель 04, 2012, 09:20:37 pm »
Итеративное добавление в АВЛ дерево займет O(n*lon(n)) времени. Быстрее сделать сортировку.

Вообще по каким критериям оптимизируем?
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"