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

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #30 : Апрель 05, 2012, 12:10:59 pm »
Кто нибудь видит "узкое" место  в этой схее?  ;)  :D

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #31 : Апрель 05, 2012, 12:23:49 pm »
схеме,  verily

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #32 : Апрель 06, 2012, 03:04:38 pm »
Да . а кривым местом в приведенной схеме является - разрешение коллизий. Пусть у нас есть 10000000 УНИКАЛЬНЫХ строк... приведенная схема поиска свободных мест  хороша, когда занято менее половины доступных ячеек... представьте ситуацию когда их менее 5% в поисках  свободных ячеек мы вынуждены будем рыскать практически по всему 10 лимонному массиву.. а это не кошерно (несмотря на то, что сама процедура примитивна и крайне эффективна). В этом, господа, проявилась и грамотность работодателей если бы значений было в 10 раз меньше то этим фактором можно было бы просто пренебречь... увеличить размер массива в 2 - неразумно... по этому на практике приходится  применять "адаптивные" методики разрешения коллизий.

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #33 : Апрель 06, 2012, 03:06:46 pm »
2 Алексей - задачка не настолько проста.. и те кто задает их - весьма непростые люди...

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #34 : Апрель 06, 2012, 03:31:51 pm »
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет?  :)

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

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Разобраться с 100000000 строк
« Ответ #35 : Апрель 06, 2012, 03:36:20 pm »
5%
Во-первых, при 5% свободных элементов жить можно, к тому же первые-то 95% элементов будут добавлены со скоростью света. Во-вторых, массив-то можно завести и на одиннадцать миллионов и на пятнадцать. В-третьих, можно использовать не хэштаблицу описанную в "Алгоритмы и структуры данных", а хэштаблицу со списками -- она попрожорливее, но её не обязательно увеличивать когда количество элементов достигло длины хэш-массива.

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #36 : Апрель 06, 2012, 03:43:25 pm »
5%
Во-первых, при 5% свободных элементов жить можно, к тому же первые-то 95% элементов будут добавлены со скоростью света. Во-вторых, массив-то можно завести и на одиннадцать миллионов и на пятнадцать. В-третьих, можно использовать не хэштаблицу описанную в "Алгоритмы и структуры данных", а хэштаблицу со списками -- она попрожорливее, но её не обязательно увеличивать когда количество элементов достигло длины хэш-массива.

1. А с какой скоростью будут добавлены последние 100 значений
2. Можно но не РАЗУМНО
3. Можно , а можно адапивный вариант например 80% значений разбрасывается поиском новых значений - в других случаях используется добавление в некоторую структуру. а этой структурой могут быть графы различных модификаций ( например , их подвиды - списки, деревья) -я собственно намекал на это.
« Последнее редактирование: Апрель 06, 2012, 03:45:14 pm от DIzer »

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #37 : Апрель 06, 2012, 05:16:25 pm »
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет?  :)
Я бы лично сюда зупульнул бы библиотечный std::unordered_set.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #38 : Апрель 06, 2012, 05:19:13 pm »
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет?  :)

А то!

Прочитать со стандартного ввода строки и отсортировать (с возможностью последующего выяснения сколько каких):
std::multiset<std::string> set(std::istreambuf_iterator<std::string>(std::cin), std::istreambuf_iterator<std::string>());

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #39 : Апрель 06, 2012, 05:45:00 pm »
 :) Так это не сорт, а стандартная хэш таблица stl для с++, тут вот какое дело, является ли stl частью декларируемой частью инфраструктуры языка (подобно стандартным библиотекам)...  ?

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #40 : Апрель 06, 2012, 05:55:25 pm »
:) Так это не сорт, а стандартная хэш таблица stl для с++, тут вот какое дело, является ли stl частью декларируемой частью инфраструктуры языка (подобно стандартным библиотекам)...  ?
stl это часть стандартной библиотеки. Да, это часть стандарта языка.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #41 : Апрель 06, 2012, 06:01:13 pm »
СПС - мое недолгое увлечение С++ было в те времена, когда это было не так...

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Разобраться с 100000000 строк
« Ответ #42 : Апрель 06, 2012, 06:02:01 pm »
СПС - мое недолгое увлечение С++ было в те времена, когда это было не так...
Похоже это было до принятия (первого) стандарта в 1998 году.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #43 : Апрель 06, 2012, 06:07:39 pm »
СПС - мое недолгое увлечение С++ было в те времена, когда это было не так...
Похоже это было до принятия (первого) стандарта в 1998 году.
разумеется... я очень быстро понял, что на моих задачах (тех времен) его возможности не используются, на тех машинах он был слишком тяжел... короче,  реальные затраты перевешивали    потенциальную выгоду.

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #44 : Апрель 06, 2012, 06:16:16 pm »
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет?  :)
Я бы лично сюда зупульнул бы библиотечный std::unordered_set.
Посмотрел http://waqur.livejournal.com/445417.html - если  автор прав (в смысле - излагает  принципы устройства реальных контейнеров STL) - то в задницу реализацию  приведенных структур  в stl (для данной задачи) - они хороши для случаев когда данных на порядок меньше.
« Последнее редактирование: Апрель 06, 2012, 06:18:54 pm от DIzer »