Подсчет наиболее часто встречающихся элементов в итерируемом объекте
Инструмент Counter из модуля collections очень полезен. В частности, с его помощью можно узнать, какие элементы списка или, скажем, какие символы в строке встречаются чаще всего, и сколько раз.
>>> import collections >>> c = collections.Counter('helloworld') >>> c Counter() >>> c.most_common(3) [('l', 3), ('o', 2), ('e', 1)]
Три наиболее часто встречающихся буквы в строке helloworld — l (3 раза), o (2 раза) и e (1 раз).
Говнокод: по колено в коде.
Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
Python / Говнокод #4317
−94
# -*- coding: utf-8 -*- # На входе: не пустой b-массив # На выходе: словарь из 1-ого элемента # 1. Сначала составляем словарь, потом ищем максимум и возвращаем def Freq1(b): assert len(b) > 0 d = <> for x in b: # Пробегаем в цикле исходный массив d[x] = d[x] + 1 if d.has_key(x) else 1 # Если ключ уже есть, прибавляем 1, если нет, записываем 1 v = max(d, key=d.get) # v ключ из словаря соответствующий максимальному значению return # Возвращаем ответ # 2. Ищем максимум прямо при составлении словаря def Freq2(b): d = <> m, i = 0, 0 # Максимальная частота и индекс в словаре for x in b: # Пробегаем в цикле исходный массив d[x] = d[x] + 1 if d.has_key(x) else 1 # Если ключ уже есть, прибавляем 1, если нет, записываем 1 if d[x] > m: m, i = d[x], x # Запоминаем максимум и его индекс return # 3. Без использования словаря (сложность квадратичная - "тупой метод") def Freq3(b): m, i = 0, 0 # Максимальная частота и соответствующее ему значение for x in b: c = b.count(x) # Сколько раз встречается x в массиве b? if c > m: m, i = c, x return # Проверка (примитивный unit-тест) def Check(inData, expected): assert Freq1(inData) == expected assert Freq2(inData) == expected assert Freq3(inData) == expected Check(["banana", "banana", "apple", "banana", "banana", "apple", "onion"], ) Check([2, 3, 9, 3, 6, 6], ) Check([True, True, True, False, False, True], )Самый часто встречающийся элемент в массиве (3 способа).
Везде сплошной говнокод. Как ПРАВИЛЬНО найти самый часто встречающийся элемент в массиве?
Наверное, можно ещё отсортировать массив и пробежать по нему храня текущий элемент и количество и обновляя соответствующие переменные?
Запостил: denis, 09 Октября 2010
Комментарии (15) RSS
Мистер Хэнки 09.10.2010 12:44 # +1
1й вариант со словарём самый оптимальный, если у вас нет ограничений на использование памяти и т.д.
>>Наверное, можно ещё отсортировать массив и пробежать по нему храня текущий элемент и количество и обновляя соответствующие переменные?
сортировка требует времени
denis 09.10.2010 14:47 # −2
Просто мне кажется, что я считаю зачем-то количество всех элементов. Может можно как-то отсекать редко встречающиеся элементы.
Например, строить сбалансированное бинарное дерево прямо при проходе массива, в узлах будет значение:количество?
У меня плохо с алгоритмами 🙂
Мистер Хэнки 09.10.2010 16:53 # +1
>Например, строить сбалансированное бинарное дерево прямо при проходе массива, в узлах будет значение:количество?
зачем переусложнять? «За деревьями леса не видно» ©
вам надо задачу решить или на девушку произвести впечатление уровнем владения алгоритмами и технологиями? так вроде как не этим впечатляют испокон веку 🙂
xXx_totalwar 09.10.2010 17:00 # 0
>вам надо задачу решить или на девушку произвести впечатление уровнем владения алгоритмами и технологиями? так вроде как не этим впечатляют испокон веку 🙂
во-во поэтому советую ебануть теоркатом: катаморфизмы, анаморфизмы, хиломорфизмы, параморфизмы наконец.
denis 09.10.2010 17:02 # 0
Мне нужно написать самое простое решение задачи, которое удовлетворило бы её препода.
В прошлый раз в задаче поиска элемента и вставки в массив её препод сказал, что бинарный поиск ещё кое-как подходит 🙂
Я написал 5 вариантов: http://stden.livejournal.com/397391.html
roman-kashitsyn 30.06.2015 12:05 # 0
Вставку в отсортированный сырой массив без разницы как делать, ибо эта операция обречена на O(N) независимо от алгоритма. Если вообще такое понадобилось делать — значит
1) массив совсем небольшой, и проще и быстрее всего прогнать итерацию insertion sort.
2) структура данных выбрана неверно, и нужно её менять целиком; например, использовать сортированный multiset.
denis 09.10.2010 14:47 # 0
Также, может есть встроенная функция чтобы это сделать?
telnet 09.10.2010 12:45 # 0
Сессия ж нескоро, неужто уже с курсачами зажимают?
denis 09.10.2010 14:49 # 0
Да, это я помогаю знакомой девушке. Просто я ей пишу как бы я сделал (я сам только начинаю программировать на Python) и мне постоянно кажется, что мои решения не python’овские. В Java я себя чувствую намного уверенней. Я привык копаться в больших Java-проектах и уже примерно знаю что там и как делается.
telnet 09.10.2010 16:25 # +2
Тематика сайта — смехотворный код, а не взаимная помощь и не pastebin. Чтобы это понять, не нужно знание Python’а, нужно знание русского, чтобы прочитать, что написано в шапке страницы, и логика, чтобы, просмотрев хотя бы несколько страниц, убедиться в справедливости написанного. Я не модератор, чтобы указывать, да. Тут вообще модераторов нет. Но Вы не первый, кто приходит сюда за помощью, и смотреть на оффтопик лично я уже подустал. Без обид. Найдёте кусок идиотского кода на той же Jav’е — постите сюда, посмеёмся вместе, опять же.
denis 09.10.2010 14:51 # 0
Например, я почти не использую генераторы и лямбда-выражения, потому что ещё просто не чувствую когда их правильно применять (т.е. есть некоторые очевидные случаи — генерация последовательности с заданными свойствами, это понятно), а вот общее правило??
intestinalbrain 30.06.2015 11:50 # +1
from collections import Counter
dict((Counter(b).most_common()[0],))
3_14dar 30.06.2015 12:22 # 0
roman-kashitsyn 30.06.2015 12:21 # 0
> Как ПРАВИЛЬНО найти самый часто встречающийся элемент в массиве?
Если это лаба, то пофигу, лишь бы не квадратично.
Если бы это нужно сделать один раз в реальной жизни, я бы сделал так:
1) строим хэш таблицу со счётчиками за амортизированное O(N)
2) преобразуем её в массив пар за O(N)
3) строим max heap по частотам за O(log N)
4) вершина хипа — ответ за O(1)
Такой алгоритм работает за амортизированное O(N). Я почти уверен, что питоний Counter, упомянутый выше, примерно так и работает.
Если операция частая и/или может затрагивать подмассивы, гуглите Range Mode Query.
В массиве целых чисел найти наиболее часто встречающееся число
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число.Если таких чисел несколько , то определить наименьшее из них.
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Найти наиболее часто встречающееся число
Используя модуль Tkinter, создайте графический интерфейс для программы, решающий следующую задачу.
В массиве целых чисел найти наиболее часто встречающееся число
Задание. Написать алгоритм на языке С++. В массиве целых чисел из n элементов найти наиболее часто.
В массиве целых чисел размерности n найти наиболее часто встречающееся число
Здравствуйте, прошу помочь в решении задачи:sorry: В массиве целых чисел размерности n найти.
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число
Если таких чисел несколько, то определить наименьшее из них и вывести его.
4615 / 2036 / 359
Регистрация: 17.03.2012
Сообщений: 10,103
Записей в блоге: 6
Один из вариантов:
1 2 3 4
import numpy as np # пусть x - наш массив. bc = np.bincount(x) np.arange(len(bc))[bc == bc.max()].min()
Добавлено через 8 минут
Есть более простой вариант. Вместо последней строки —
bc.argmax()
Но тут мы надеемся на подходящее поведение функции в неопределённой, в общем, ситуации, а именно — что argmax из всех максимальных элементов берёт именно первый.
Регистрация: 06.05.2015
Сообщений: 7
А нельзя написать код через range?
4615 / 2036 / 359
Регистрация: 17.03.2012
Сообщений: 10,103
Записей в блоге: 6
Регистрация: 06.05.2015
Сообщений: 7
Нельзя как то проще написать код?
4615 / 2036 / 359
Регистрация: 17.03.2012
Сообщений: 10,103
Записей в блоге: 6
Сообщение было отмечено Tatiana933 как решение
Решение
Да куда уж проще-то, две строки всего.
Но можно и так, но это неспортивно:
from collections import Counter Counter(x).most_common()[0]
Там увидите, что есть что.
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
В массиве целых чисел с количеством элементов п найти наиболее часто встречающееся число
В массиве целых чисел с количеством элементов п найти наиболее часто встречающееся число. Если.
В случайном массиве целых чисел с количеством элементов N найти наиболее часто встречающееся число
В случайном массиве целых чисел с количеством элементов N найти наиболее часто встречающееся число.
В массиве целых чисел найти наиболее часто встречающееся число. Если таких чисел несколько, то определить наим
Вообщем не понял сути самого задания. Разъясните иль если сможете помогите сделать.
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если таких чисел несколько, то
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если.
Задан массив из k чисел. Найти число, наиболее часто встречающееся в этом массиве
Основная проблема в том, что нельзя использовать сторонние библиотеки, даже функцию sort, в общем.
Задан массив из k чисел. Найти число, наиболее часто встречающееся в этом массиве
Задан массив из k чисел. Найти число, наиболее часто встречающееся в этом массиве
Поиск часто встречающихся элементов в массиве
Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.
Казалось бы, чего тут думать? Возьмём Dictionary, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?
Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?
К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву. Алгоритм Бойера-Мура — тех самых Бойера и Мура, что придумали намного более известный алгоритм поиска подстроки — проще всего представить следующим образом: на вечеринке собрались N людей, и на каждом по одному элементу из массива. Когда встречаются двое, у которых элементы разные, они присаживаются это обсудить. В конце концов останутся стоять только люди с одинаковыми элементами; очевидно, это тот самый элемент, который встречался больше N/2 раз.
Реализация алгоритма Бойера-Мура занимает всего несколько строк:
int* majority(int[] array, int N) < int confidence = 0; // количество людей, не нашедших пары и оставшихся стоять int* candidate = NULL; // последний человек, не нашедший пару -- // возможно, его элемент встречается чаще всего // проходим по массиву и усаживаем пары с разными элементами for (int i = 0; i// иначе следующий либо садится с одним из стоящих, // либо будет стоять вместе с ними, если у него такой же элемент else if (*candidate == array[i])) confidence++; else confidence--; > return confidence > 0 ? candidate : NULL; > 
В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.
Усложним задачу. Теперь в массиве длиной N надо найти элементы, которые повторяются больше N/3 раз — если есть два, то оба, если есть один, то один.
Например, нашему устройству с маленькой памятью нужно принять двоичный сигнал с неизвестными уровнями нуля и единицы, но известно, что примерно половину времени передаётся ноль, примерно половину времени — единица, а любые отличные от них уровни сигнала — это помехи и дребезг от переключения.
Идею прошлого алгоритма несложно обобщить и для троек: пусть люди с разными элементами рассаживаются по трое. Значит, в конце вечеринки останутся стоять люди максимум с двумя разными элементами. Если какой-то элемент встречался больше N/3 раз, значит человек с ним гарантированно останется стоять, ведь сидящих троек получится не больше N/3. Как и в прошлом случае, если искомые элементы существуют — то они будут найдены, но если их нет — то найтись может кто попало.
Код мало отличается от предыдущего: по-прежнему один проход по массиву и O(1) дополнительной памяти.
void majority(int[] array, int N, int** cand1, int** cand2) < int conf1 = 0, conf2 = 0; // количество стоящих людей с двумя элементами *cand1 = NULL; *cand2 = NULL; // два стоящих человека с разными элементами // проходим по массиву и усаживаем тройки с разными элементами for (int i = 0; i0 && **cand1 == array[i]) conf1++; else if (conf2 > 0 && **cand2 == array[i]) conf2++; else // может, стоят только с одним элементом, или вообще стоящих нет? if (conf1 == 0) < *cand1 = array+i; conf1++; >else if (conf2 == 0) < *cand2 = array+i; conf2++; >else < // стоят с двумя другими элементами, так что усаживаем всю тройку conf1--; conf2--; >> if(conf1 == 0) *cand1 = NULL; if(conf2 == 0) *cand2 = NULL; > Этот алгоритм опубликован в 1982 американскими учёными Джаядевом Мисрой и Дэвидом Грисом (Jayadev Misra & David Gries), и в их работе используется более скучная метафора — мешок с N числами, из которого они извлекают по 3 разных числа за каждую операцию. Кроме того, их псевдокод не похож ни на один понятный современному программисту язык. Мне больше понравилось объяснение их алгоритма в позапрошлогоднем конспекте лекций американского профессора Амита Чакрабарти.
В наиболее общей форме, когда в массиве длиной N надо найти элементы, которые повторяются больше N/k раз — придётся-таки воспользоваться словарём. Хранить в словаре мы будем только те элементы, с которыми люди стоят — т.е. не больше k-1 записей.
int[] majority(int[] array, int N, int k) < // словарь стоящих людей изначально пуст Dictionarycandidates = new Dictionary<>; // проходим по массиву и усаживаем группы по k for (int i = 0; i return candidates.Keys.ToArray(); > В этой наиболее общей форме алгоритма — по-прежнему один проход по массиву и O(k) дополнительной памяти. Если мы пользуемся для реализации словаря хэш-таблицей, а все записи в словаре свяжем в список — тогда общая сложность алгоритма останется линейной: строчка (*) с удалением записи из словаря выполняется самое большее N раз, ведь на каждой итерации основного цикла в словарь добавляется не больше одной записи. Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.
Таким образом наше устройство с маленькой памятью смогло бы общаться с одним пушистым зверьком, недавно препарированным хабраумельцами. Сигналы этого зверька имеют пять логических уровней: полагаем k=6, и получаем все пять уровней прямо на ходу, даже без сохранения сигнала в память. Нужно только обеспечить протоколом, чтобы все пять уровней встречались в сигнале одинаково часто.
Для алгоритма Мисры-Гриса упоминаются и другие применения. Например, можно следить в реальном времени за трафиком в сети, и если некий один хост потребляет непропорционально большую часть трафика — начинать расследование. Так же можно следить за кликами по баннерам, за финансовыми транзакциями, за потоком инструкций в моделируемом процессоре… В общем, всюду, где большое число повторений — подозрительная аномалия.
За оживление текста иллюстрациями надо благодарить Nitatunarabe
- алгоритм бойера-мура
- алгоритм мисры-гриса
- сложность алгоритма
- обработка сигналов
- computer science
- индусы
- Высокая производительность
- Data Mining
- Алгоритмы