Вопрос по коду

Мои результаты такие модифицированной программы куропаткина

161639 ms и 300894 ms

Да ладно тебе. Ну работал код у чувака 200 секунд, ну станет 198 - все равно уже никакой отзывчивости интерфейса :-)

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

Э-э-э не. За вложенностью-то следи (да, может юзать для неё отступы - и плохая идея, но пхытон есть пхытон) :

...
  if word in counts.keys():
    counts[word] = 0 # создаст элемент
  count[word] += 1 # инкрементирует его

То есть count[word] += 1 выполнится всегда.

Хм, кстати код-то у меня там неверный, но дело не в 0 частности и не в алгоритме в целом :-)

А, сорян, это уже я туплю.

Предлагаю проигнорировать этого господина.

Смысл его наказывать? Он уже себя сам наказал.

Попробуй ещё std::ios::sync_with_stdio(false)

Однако...
1,50s user 0,02s system 99% cpu 1,530 total

Тут ещё выяснится, что твой калькулятор быстрее моего.

Не быстрее, но близко :)

Я забыл сказать, что в твоём коде ещё поменял isalnum на isalpha. Это было ближе к исходной задаче, и ещё работало быстрее.

Я обычно так делаю:

count = {}
for word in words:
    count[word] = count.get(word, 0) + 1

Ваш код , с моими подправками работает быстрее всех, только буст не смотрел. Вот вам бы подправить его потому что там слова которых нет в исходном файле. Код смотрите на моей ссылке один из закоментированных

Ваша программа работает тоже быстро только на выходе слова с точками и прочими запятыми, я ее отредактировал смотрите по ссылке (закомментированная)

По качеству лучше остальных только отсортировать по алфавиту нужно , программа в ссылке

В вашем коде на выходе в словах есть скобки да апострофы

anonymous, invy, alex4321

https://www.youtube.com/watch?v=EFKLN4jbwhA

LOL

:-)

У вас хорошее чуство юмора)

Вообщем ваш код помог, но меня завалили на собеседовании вопросом о быстрой сортировке

к примеру, про std::unordered_map

Я бы на самом деле лучше бы не советовал анордеред мап джуниорам. В принципе его польза и так под вопросом. Да O(1) оно конечно круто, но обычная мапа тоже довольно быстрая. Но вот памяти unordered_map жрет конечно на порядок больше.

Зачем сортировать, то что можно записывать в само сортирующуюся структуру данных, да еще с поиском O(log(n))?

и еще там надо отсортировать по алфавиту

std::map

но меня завалили на собеседовании

Тебе ещё повезло, что они этой темы не видели.

но обычная мапа тоже довольно быстрая

А если сравнение не дешёвое?

Но вот памяти unordered_map жрет конечно на порядок больше.

Почему?

и еще там надо отсортировать по алфавиту

std::map

Вообще говоря, нет. Сортировка по значениям байт не обязательно совпадает с сортировкой по алфавиту.

Вообще говоря, нет. Сортировка по значениям байт не обязательно совпадает с сортировкой по алфавиту.

Можно свой компаратор же добавить. Шаблонный параметр для функтора компаратора который возвращает результат сравние по операции «<» же есть.

Почему?

Хэш-таблица же. Там по идее считается индекс в массиве (грубо говоря конечно) по HASH(key) % size

Если много коллизий возникает, то мы должны резко увеличить размер массива (раза в два) и пересчитать/переместить все старые элементы по новым местам. То есть там памяти обычно выделено гораздо больше чем надо, чтобы исключить коллизии. Иначе это не хэш-таблица уже=)

И вообще для std::string будет юзаться

std::string::operartor<

То есть для ANSI строк работает.

Можно свой компаратор же добавить.

Можно. Но есть нюанс.

Компаратор определяет порядок ключей. В конечном итоге определяет, будут ли два слова считаться одинаковыми. Возможна ситуация, когда регистр букв важен при подсчёте слов, но не важен при сортировке результатов.

Но конечно же, есть ситуации, где это одно и то же.

Иначе это не хэш-таблица уже=)

Разве хеш-таблица гарантирует отсутствие коллизий?

И разве элементы с одинаковым хешем не тупо в список организуются и поиск по нему идёт уже линейно?..

И разве элементы с одинаковым хешем не тупо в список организуются и поиск по нему идёт уже линейно?

Есть linear probing. В этом случае элементы живут прямо в корзинах, по одному. Если при чтении обнаружилось, что ключ не совпадает, проверяют следующие корзины, пока не встретят пустую или не совпадёт ключ. Аналогично при записи. При удалении сложнее, там нужно поддерживать связность. Вообще это целый класс, там есть варианты с использованием нескольких хеш-функций, варианты с перехешированием и перераспределением элементов при коллизиях. Много всего.

Да, но тогда это уже не O(1). Ну оно в списки и суется, но когда самый длинный список становится длинее некоего N мы ресацзим и перехэшируем. Т.е. определенное кол-во коллизий допустимо, но немного.

А, ну и это тоже

Да, но тогда это уже не O(1).

А (плюсовый) стандарт и не гарантирует O(1). Обещается:

Complexity: Average case O(1), worst case O(size()).

Опять же, функцию хеширования можно подсунуть свою, пусть даже возвращающую всегда 0. И что тогда будет делать контейнер?

В общем, у меня есть большие сомнения, что в рантайме контейнер будет что-то делать в зависимости от количества коллизий. Как по мне, тупо будет падать скорость.

Много всего.

Это всё хорошо, но мне по прежнему интересно заявление, что хеш-мапа жрёт «на порядок больше» обычной мапы.

но мне по прежнему интересно заявление, что хеш-мапа жрёт «на порядок больше» обычной мапы.

Мне тоже интересно посмотреть на сравнение.

Я на mvs проаерял, там разница вообще дикая была. Сотня мб обысной мапы, против пары гб хэшированной. Можно будет потом и на онтопике проверить.

Может и запилю.

Не видели потому что код сныкан в облаке, а не тупо на форуме выложен , а те части ,что выложены я подправил и целиком их не найти

Ты такой хитрый.

Что за структура такая?

Что значит этот комментарий?

Вы очень похожи на ребят которые меня собеседовали, Хахаха

Забавно, но я об этом и не думал вначале , когда тему создавал

Я себя наказал, когда задумал изучить этот язык

Бинарное дерево поиска. Можешь почитать википедию. Оно еще самобалансирующимся может быть. Так, вот std::map является по сути таким деревом с поиском O(log(n)) да еще при его обходе

for (auto iter : Map) {
}

или

for (auto iter = Map.begin(); iter != Map.end(); ++iter) {
}

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

Значит, что достаточно использовать std::map с ключом word и значением count, вместо std::list структур {string word; int count} Для получения бинарного поиска и отсортированных данных в самом конце.

Ты себя наказал когда решил программистом стать, у тебя на лицо тотальный провал базовых знаний уровня 1-2 курса. Если ты задаешь вопросы

Что за структура такая?

на

Зачем сортировать, то что можно записывать в само сортирующуюся структуру данных, да еще с поиском O(log(n))?

Ты о чем вообще? Ты собеседуешься на джуниора и то я считаю, что тебе повезет если тебя куда-то возьмут, а гонора у тебя как у прогера с 10 летним стажем. Уже стебешься над людьми собеседования проводящими, а знаний у тебя ноль.