![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaХорошая программистская задачка:
Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).
Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.
P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.
Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).
Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.
P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-07-11 06:30 pm (UTC)no subject
Date: 2004-07-11 06:36 pm (UTC)Но в принципе в условии задачи не сказано, можно ли модифицировать список. Ясно, что лучше обойтись без модификации, но я не скажу, можно без неё обойтись или нельзя ;)
(no subject)
From:no subject
Date: 2004-07-11 06:44 pm (UTC)no subject
Date: 2004-07-11 06:47 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2004-07-11 06:49 pm (UTC)no subject
Date: 2004-07-11 07:21 pm (UTC)no subject
Date: 2004-07-11 07:33 pm (UTC)Но требует дополнительной памяти, линейной от размера исходного списка (для хранения промежуточных данных во время рекурсивных вызовов алгоритма для нахождения медианы).
(no subject)
From:(no subject)
From:(no subject)
From: (Anonymous) - Date: 2004-07-14 01:44 am (UTC) - ExpandHotja net, ne prav
From: (Anonymous) - Date: 2004-07-14 02:24 am (UTC) - Expandno subject
Date: 2004-07-11 07:27 pm (UTC)(no subject)
From:no subject
Date: 2004-07-11 07:52 pm (UTC)no subject
Date: 2004-07-11 08:35 pm (UTC)no subject
Date: 2004-07-11 08:02 pm (UTC)Если разделить список на пары, то если член "х" –– большинство, то, если искомый член "х" есть, то, если пары, где члены разные, повыкидывать, то
число пар, где оба члена –– "х" должно быть больше, чем число пар, где оба члена –– "не х". Как предельный случай можно поиграть со списком их а+1 белых и а–1 черных.
Значит действуем так: игнорируем все смешанные пары и ставим счетчик на 0. Идем до первой одинаковой пары, замечаем ее члены как кандидата на большинство, ставим счетчик на 1. Если следующая одинаковая пара такая же, то увеличиваем счетчик на 1, если она другая, вычитаем из счетчика 1. Если счетчик оказывается на 0, то следующая одинаковая пара дает нам кандидата и 1 в счетчике.
В процессе узнаем сколько членов в списке.
Если в конце процесса имеем не 0 в счетчике и кандидата, то на следующем прогоне считаем сколько найдем кандидата в списке. Если >50%, ура.
На нечетное число членов тривиально распространимо, но писать лень.
no subject
Date: 2004-07-11 08:20 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:Ага, уразумел
From:(no subject)
From: (Anonymous) - Date: 2004-07-12 03:08 am (UTC) - Expand(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2004-07-11 10:22 pm (UTC)Одно слово: хэширование.
no subject
Date: 2004-07-11 10:46 pm (UTC)(no subject)
From:no subject
Date: 2004-07-12 01:14 am (UTC)no subject
Date: 2004-07-12 01:44 am (UTC)no subject
Date: 2004-07-12 03:09 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:улучшение, вроде
From: (Anonymous) - Date: 2004-07-13 03:51 pm (UTC) - Expand(no subject)
From:Re: улучшение, вроде
From:Nemnogo drugoe reshenie. Nabrosok idei
Date: 2004-07-12 04:22 am (UTC)Voz'mem nebol'shoj massiv (naprimer 10 elementov). Kazhdyj element massiva - para: element-chastota elementa. Budem zapisyvat' v nego elementi po mere postuplenia a zaodno i schitat' ih kolichestvo (chastotu). Kak tol'ko nam vstretit'sja 11-i element, nachnem zapolnjat' vtoroj takoj zhe massiv. Kogda vtoroj massiv okazhetsja zapolnennym, soljem dva massiva v odin, t.e. vyberem iz 20 elementov 10 s maksimal'nymi chastotami. Ochistim vtoroj massiv i stanem zapolnjat' ego snova, poka nam opjat' ne popadetsja 11-i element. Opjat' soljem 2 massiva (ili viberem 10 maksimalnih) i t.d. V konce u nas budet iskomyj element odnim iz 10 v pervom massive. Teper' delaem eshe odin prohod, podschityvaja chastoty tol'ko etih 10 elementov - i togda u nas budet okonchatel'nyj otvet.
Vozmozhno 10 elementov - dazhe bol'she chem nuzhno. Vpolne verojatno 2-3 dostatochno.
Algoritm rabotaet, dazhe esli elementy - ne chisla i predstavit' ih v vide korotkoj stroki ne predstavljaetsja vozmozhnym.
Ne znaju poka kak obosnovat', no dumaju chto esli element zanimaet bol'she poloviny spiska, to ego nevozmozhno raspredeli't po spisku takim obrazom, chtobi on ne popal v okonchatel'nyj massiv.
no subject
Date: 2004-07-12 04:23 am (UTC)Для удобства рассмотрим этот список как кольцо (мысленно замкнем начало с концом). Если значение X встречается больше чем в 50% элементов, то в кольце обязательно будут последовательности подряд идущих X-ов, причем длина максимальной такой цепочки будет больше всех других последовательностей подряд идущих одинаковых элементов.
За один проход находим максимальную цепочку одинаковых значений X, за второй - убеждаемся, действительно ли X-ов больше 60% в списке.
no subject
Date: 2004-07-12 04:37 am (UTC)no subject
no subject
Date: 2004-07-12 10:55 am (UTC)Гeнeрируются случайная послeдоватeльность ( можно - по кругу, eсли выборка конeчная - с остатком от дeлeния по модулю N ) с попарным
сравнeниeм номeров, совпали + 1, нe совпали: -1, вeдeм сумму и сравниваeм с заранee выбранной константой...
no subject
Date: 2004-07-12 02:26 pm (UTC)no subject
Date: 2004-07-12 02:32 pm (UTC)Нет:
1 1 1 2 2 3 2 2 3 2 2 3 2 2 3
no subject
Date: 2004-07-12 02:31 pm (UTC)no subject
Date: 2004-07-12 02:43 pm (UTC)no subject
Date: 2004-07-12 03:41 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Dokazatelstwo otloszhil a tut i kontr-primer nashelsya.
Nedarom avva kogda-to pisal kak ostorozhno nuzno otnsoistsya k swoej intiuicii.
no subject
Date: 2004-07-12 04:18 pm (UTC)no subject
Date: 2004-07-13 09:46 am (UTC)Если объекты однобитные +1 и -1, тогда N if'ов и N операций (например, суммирования).
IFы нужны, собственно, если они НЕ +1 и -1.
Если битов в объекте K, тогда в К раз больше работы.
Предполагается простейший набор команд процессора.
no subject
Date: 2004-07-17 06:07 pm (UTC)Пускай мы будем работать с двубайтными значениями (16 бит, 64 К значений). Заводим дополнительный массив размером 256 Кб (64К * 4 байта), сбрасываем все в нолики.
Первый проход - берем младшие 16 бит от каждого числа нашей последовательности, считаем их индексом в нашем массиве и увеличиваем соответствующий элемент в доп-массиве на 1.
После этого бежим по доп-массиву и ищем самое большое число. Для правильного решения такое число будет всего одно, поэтому можно не беспокоиться о том, что оно может встретиться несколько раз.
Если это число меньше или равно половине количества элементов в последовательности, то говорим "решения нет".
В противном случае запоминаем егойный индекс ("subValue", что представляет собой значение младших 16 бит нашего "подозрительного" числа).
Опять обнуляем доп-массив и бежим по нашей последовательности. Но теперь обрабатываем (а) только те элементы, у которых младшие 16 бит равны "subValue" и (б) в качестве "индекса" используем старшие 16 бит.
Снова бежим по доп-массиву и ищем самое большое число.
Если его находим и оно больше половины количества элементов, то получаем решение, в противном случае - "решения нет".
*******
Если кому-то кажется, что 256 Кб на доп-массив - это слишком много, то есть одно объяснение и один обходной маневр.
Объяснение: мне нравится работать или думать об очень больших последовательностях. Которые, например, могут занимать 4-8 Гб (до 2 миллиардов значений). В этом случае наши дополнительные затраты выглядят весьма смешными, зато скорость повышается достаточно сильно (потому что всего два обхода последовательности).
Обходной маневр: будем работать с байтами. Правда, получается до 4х итераций по нашей последовательности, зато затраты на дополнительную память уменьшаются до 1 Кб (не считая нескольких переменных для хранения индекстов, "subValue" и так далее).
*******
Конечно, если вдруг в нашей последовательности будет более 4 миллиардов значений, элементы доп-массива должны иметь разрядность более 32 бит (дабы не произошло перехода через 0). Но и это обходится - будем занимать не 256 Кб, а 512.
no subject
Date: 2004-07-18 04:44 pm (UTC)(no subject)
From:no subject
Date: 2004-08-02 04:39 am (UTC)$candidate = 0;
foreach ($numbers as $n)
{
$sum += $n;
if (!isset($min_diff)) $min_diff = $n;
$diff = ($sum / count($sum) - $n);
if ($diff <= $min_diff)
{
$candidate = $n;
$min_diff = $diff;
}
}
echo $candidate;
Набросок идей. Практическую ценность не проверял