Oberon space
General Category => Общий раздел => Тема начата: DIzer от Апрель 04, 2012, 06:28:39 pm
-
Есть топик находящийся в файле возможно с повторениями -вывести уникальные строки и количество их повториений- мой выбор АВЛ -дерево -кто может подсказать лучшее решение?
-
Тупо отсортировать файл. ;)
-
http://spherix.jeka.ru/forum/viewtopic.php?id=1764 (http://spherix.jeka.ru/forum/viewtopic.php?id=1764)
-
Тупо отсортировать файл. ;)
А чем это лучше моего предложения (кроме тупости, конечно)?
-
Тупость важный параметр! :D
Ну а кроме... меньшим расходом оперативы. Сколько файл гигов то?
-
Тупость важный параметр! :D
Ну а кроме... меньшим расходом оперативы. Сколько файл гигов то?
НУ пусть в среднем строка -20 байт...
-
Ну вот 2 гига... У меня например никогда столько свободной памяти нет...
Я конечно не знаю сколько юниксовая утилита памяти жрет (по ссылке, что я приводил), но можно сортировкой слиянием сделать :)
-
Ох ты -еть... :) я лишний нолик приписал, однако.... в файле 10 миллионов строк то есть около 200мб
-
О как! :o
Ну тогда номенклатура алгоритмов ни чем не ограничена :)
Опять же - сортирнуть можно в памяти. Если задача одноразовая, то я сложными алгоритмами не заморачивался бы.
-
Шо значить не ограничена... я же просил ЛУЧШЕЕ решение, ну и с обоснованием (так сказать защита от тупости) ;D что бы не было пузырька в самой тупой ипостаси...(2 йной for)
-
Да , кто нибудь делал итеративное добавление в АВЛ дерево?
-
Шо значить не ограничена... я же просил ЛУЧШЕЕ решение, ну и с обоснованием (так сказать защита от тупости) ;D что бы не было пузырька в самой тупой ипостаси...(2 йной for)
Задача практическая или образовательная?
Если практическая, то юникс утилита - это готовое решение. (там точно не пузырек :))
-
:) Трудно сказать (кому как)... это одна из 2 "конкурсных" задач для трудоустройства в одну из контор (обьявление я увидел рядом с деканатом) - по идее, считаю , что такого уровня задачи студенты 1 курса должны брать (ну процентов 10 точно, при желании, конечно)...
-
Странная задача для трудоустройства. А что там за сфера деятельности у работодателя?
Сдается мне, что в этом случае правильность алгоритма зависит от тараканов интервьювера ;)
-
Итеративное добавление в АВЛ дерево займет O(n*lon(n)) времени. Быстрее сделать сортировку.
Вообще по каким критериям оптимизируем?
-
Задача не полна без её "приземления". Например может оказаться что у нас памяти больше нет ВООБЩЕ (ну. то есть памяти есть O(1)). Тогда нужно трансформировать данные на месте.
Либо памяти у нас завались и надо сделать как можно быстрее.
Либо у нас память бывает разная - очень быстрая, но мало, средне средней и завались медленной. Все данные целиком единым куском влазят только в медленную. Оптимизируем по скрости.
Ну и так далее. Кроме всего прочего, разные операции могут еще по разному стоить (сравнение - одна стоимость, копирование - совсем уже другая).
Также операции (некоторые) в некоторых случаях могут векторизироваться.
Ну и т.д. и т.п.
Поэтому, на собеседовании, когда я человеку коварно даю алгоритмическую задачку и НЕ уточняю вешеперечисленные особенности, я обычно ожидаю либо увидеть самое простое (и потому поддерживаемое) решение, либо услушать множество уточняющих вопросов (на которые я обычно говорю - после узнаешь, ты напиши для начала как-нибудь).
-
Итеративное добавление в АВЛ дерево займет O(n*lon(n)) времени. Быстрее сделать сортировку.
Вообще по каким критериям оптимизируем?
Не делал (по этому и интересуюсь) , рекурсивное log2 (n)+20-40%. вообще задача забавная... а контора.. --mmorpg клепатели :) , обычное добавление (в простое BSD) vs рекурсивным дает 10-15% выигрыша (память не считаем...). По всем, основной - время -Предлагаю просто оценить задачу (возможное решение) без реализации :)
-
BST - не BSD, конечно.
-
А если тупо хэш? (коль уж у нас памяти не меряно)
Будет, как я понимаю, O(n)
-
А если тупо хэш? (коль уж у нас памяти не меряно)
Будет, как я понимаю, O(n)
А что есть идеи как подобрать хэш функцию дающую открытую адресацию по такого рода набору данных?
-
было бы конечно круто... :) ведь набор данных известен... но я такой методы не знаю :( :)
-
А что есть идеи как подобрать хэш функцию ... ?
Это вообще не проблема. Эффективность произвольной "вменяемой" хэшфункции на большой выборке очень слабо отличается от теоретического предела 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 Мб, то есть отдельные объекты-строки не создавать ибо достаточно будет запомнить (в другом массиве) начальные индексы строк (кстати, длины строк тоже не обязательно запоминать ибо их можно вычислить по разности соседних индексов).
-
Ежели будет использовано не отображение файла в память, а чтение в массив букв, то повторные строки в него, конечно, писать не нужно.
-
Наверно, во время собеседования немаловажно узнать ход рассуждений. Узнать почему выбран тот или иной способ решения, между какими другими вариантами были колебания.
-
Наверно, во время собеседования немаловажно узнать ход рассуждений. Узнать почему выбран тот или иной способ решения, между какими другими вариантами были колебания.
Угу. Потому я и описал примерный ход беседы когда я провожу собеседование.
-
А что есть идеи как подобрать хэш функцию ... ?
Это вообще не проблема. Эффективность произвольной "вменяемой" хэшфункции на большой выборке очень слабо отличается от теоретического предела 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. А вот со вторым - ОК (все по делу) :)
-
Наверно, во время собеседования немаловажно узнать ход рассуждений. Узнать почему выбран тот или иной способ решения, между какими другими вариантами были колебания.
Угу. Потому я и описал примерный ход беседы когда я провожу собеседование.
Да, с учетом того что задача дается "факультативно" - потенциальный работодатель вполне может (и должен ИМХО) рассчитывать на "взвешенное" решение.
-
Разобрать файл, закачать в MSAccess. Потом можно резвиться как угодно - сортировать вперед-назад, считать количество уникальных, количество повторений и пр.
Если Access не подходит по религиозным соображениям - заменить.
-
;) Как вариант пойдет ( как использование сторонней реализации работы с одним из видов B- деревьев) - но вот помню еще лет 10 назад он хреновато работал на данных такого обьема...
-
Но вопрос, зачем? Сергей довольно детально изложил нормальную схему действий
1. Строим хэш функцию отображающую строку на 0..9999999 (с коллизиями)
2. Создаем массив указателей на подходящую структуру
3. Для каждой строки вычисляем хэш, пытаемся запихнуть в массив если ячейка пуста, то создаем структуру (запихиваем строку, количество повторений) если занята - сравниваем хранящиеся строки -если они равны увеличиваем счетчик иначе ищем свободную ячейку создаем структуру в ней...(т.е. разрешаем коллизии)... ну а после этого неблагодарного дела пробегаемся по массиву еще раз и формируем выходной файл...
Остальные оптимизации... дело вкуса.
-
Кто нибудь видит "узкое" место в этой схее? ;) :D
-
схеме, verily
-
Да . а кривым местом в приведенной схеме является - разрешение коллизий. Пусть у нас есть 10000000 УНИКАЛЬНЫХ строк... приведенная схема поиска свободных мест хороша, когда занято менее половины доступных ячеек... представьте ситуацию когда их менее 5% в поисках свободных ячеек мы вынуждены будем рыскать практически по всему 10 лимонному массиву.. а это не кошерно (несмотря на то, что сама процедура примитивна и крайне эффективна). В этом, господа, проявилась и грамотность работодателей если бы значений было в 10 раз меньше то этим фактором можно было бы просто пренебречь... увеличить размер массива в 2 - неразумно... по этому на практике приходится применять "адаптивные" методики разрешения коллизий.
-
2 Алексей - задачка не настолько проста.. и те кто задает их - весьма непростые люди...
-
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет? :)
-
5%
Во-первых, при 5% свободных элементов жить можно, к тому же первые-то 95% элементов будут добавлены со скоростью света. Во-вторых, массив-то можно завести и на одиннадцать миллионов и на пятнадцать. В-третьих, можно использовать не хэштаблицу описанную в "Алгоритмы и структуры данных", а хэштаблицу со списками -- она попрожорливее, но её не обязательно увеличивать когда количество элементов достигло длины хэш-массива.
-
5%
Во-первых, при 5% свободных элементов жить можно, к тому же первые-то 95% элементов будут добавлены со скоростью света. Во-вторых, массив-то можно завести и на одиннадцать миллионов и на пятнадцать. В-третьих, можно использовать не хэштаблицу описанную в "Алгоритмы и структуры данных", а хэштаблицу со списками -- она попрожорливее, но её не обязательно увеличивать когда количество элементов достигло длины хэш-массива.
1. А с какой скоростью будут добавлены последние 100 значений
2. Можно но не РАЗУМНО
3. Можно , а можно адапивный вариант например 80% значений разбрасывается поиском новых значений - в других случаях используется добавление в некоторую структуру. а этой структурой могут быть графы различных модификаций ( например , их подвиды - списки, деревья) -я собственно намекал на это.
-
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет? :)
Я бы лично сюда зупульнул бы библиотечный std::unordered_set.
-
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет? :)
А то!
Прочитать со стандартного ввода строки и отсортировать (с возможностью последующего выяснения сколько каких):
std::multiset<std::string> set(std::istreambuf_iterator<std::string>(std::cin), std::istreambuf_iterator<std::string>());
-
:) Так это не сорт, а стандартная хэш таблица stl для с++, тут вот какое дело, является ли stl частью декларируемой частью инфраструктуры языка (подобно стандартным библиотекам)... ?
-
:) Так это не сорт, а стандартная хэш таблица stl для с++, тут вот какое дело, является ли stl частью декларируемой частью инфраструктуры языка (подобно стандартным библиотекам)... ?
stl это часть стандартной библиотеки. Да, это часть стандарта языка.
-
СПС - мое недолгое увлечение С++ было в те времена, когда это было не так...
-
СПС - мое недолгое увлечение С++ было в те времена, когда это было не так...
Похоже это было до принятия (первого) стандарта в 1998 году.
-
СПС - мое недолгое увлечение С++ было в те времена, когда это было не так...
Похоже это было до принятия (первого) стандарта в 1998 году.
разумеется... я очень быстро понял, что на моих задачах (тех времен) его возможности не используются, на тех машинах он был слишком тяжел... короче, реальные затраты перевешивали потенциальную выгоду.
-
Мне вот интересно Vlad запульнул бы библиотечный сорт для решения этой задачи или нет? :)
Я бы лично сюда зупульнул бы библиотечный std::unordered_set.
Посмотрел http://waqur.livejournal.com/445417.html (http://waqur.livejournal.com/445417.html) - если автор прав (в смысле - излагает принципы устройства реальных контейнеров STL) - то в задницу реализацию приведенных структур в stl (для данной задачи) - они хороши для случаев когда данных на порядок меньше.
-
Посмотрел http://waqur.livejournal.com/445417.html (http://waqur.livejournal.com/445417.html)
Кстати, я когда хэштаблицу увеличиваю, то хэшкоды от ключей не перевычисляю :) :) :) Просто с самого начала я вычисляю хэшкод h не по модулю длины таблицы N, а целый uint, то есть по модулю 2^32 и запоминаю его. Естественно индексируюсь по индексу i = h mod N. Затем, когда N увеличивается до N' мне не нужно перевычислять хэшкоды от объектов, а достаточно просто индексироваться по i' = h mod N'. Более того, когда ищу элемент в списке линейным поиском, то сначала проверяю равенство полных uint-ных хэшкодов и лишь если они равны (вероятность случайного совпадения одна четырёхмиллиардная), то проверяю на точное равенство ключи. Летает со скоростью света.
-
я про это и написал.. когда давал общую схему расчета Петру - она очевидна (я не имею в иду расширение таблицы) - в этой задаче это ВОЗМОЖНО но НЕРАЗУМНО а вот если хранить не 10 лимонов 20 байтных строк а 8 байтные числа с плавающей точкой - то ВПОЛНЕ :)