[алгоритмы] подсчет частот вхождения чисел в массив

числа какого типа?

real

как правило, массив нужно отсортировать(quick sort) и потом бинарным поиском

что-то мне подсказывает завести хеш-таблицу пар (число, кол-во вхождений) и за O(n) ее заполнить.

Встроенными средствами ЯП.

> ... и потом бинарным поиском
А что делать бинарным поиском?

массивы на входе отсортированные по возрастанию. в результате нужен массив массивов (значение, частота).

попробую вариант с бинарным поиском. больше вариантов нету?

Советую еще раз повторить материал по скорости работы алгоритмов.
Ну вот же Вам предлагают: [алгоритмы] подсчет частот вхождения чисел в массив (комментарий)

Или Вам во что бы то ни стало необходимо считать за <O(n).

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

// STD
#include <cstdio>
#include <ctime>
#include <vector>
#include <tr1/unordered_map>

using std::vector;
using std::tr1::unordered_map;

int main( void )
{
    vector<float> data( 1000000 );

    for( size_t i = 0 ; i < 1000000 ; ++i )
        data[ i ] = rand() / ( rand() + 1.f );

    clock_t start = clock();

    unordered_map<float,size_t> counts;
    for( size_t i = 0 ; i < 1000000 ; ++i )
        counts[ data[ i ] ]++;

    printf( "%f secs\n", ((double) (clock() - start)) / CLOCKS_PER_SEC );
}

выполнилось за 0.2 сек

man std::lower_bound + арифметика итераторов.

> man std::lower_bound + арифметика итераторов.

для одного числа и сортировать не надо, а для многих - твои std::lower_bound + арифметика итераторов сосут, не считая того, что неизвестно можно ли менять исходные данные - итого приплюсуй копирование

Я вот, помнится, вопрошал про быстрый алгоритм построения гистограммы, так мне еще советовали вспомнить radix sort.

Да и вообще, можно просто разбить диапазон изменения значения содержимого массива на N частей и построить гистограмму. Если надо уточнить - уточнить нужный участок. Все проще, чем сортировать все.

Хотя, конечно, можно воспользоваться способом aho, т.е. построить динамическую гистограмму. Но, сдается мне, что «обычная» гистограмма, пусть даже и с последующим уточнением, будет считаться быстрей.

Что ты курил, где алгоритм меняет данные? про сложность и посасывание lower_bound почитай в мануале. Кстате, твой пример сверху за каким-то хреном жрет память. lower_bound просто бежит по массиву.

> выполнилось за 0.2 сек
Если учесть, что данные отсортированы, и выкинуть ненужную хеш-таблицу, еще быстрей будет.

> Что ты курил, где алгоритм меняет данные?

не курил, просто не увидел, что ТС потом в обсуждении уточнил, что данные отсортированны

Стоить гистограмм ненужно, тк ТС написал, что данные уже отсортированы ;)

> нашли и бежим по массиву(направление можно взять из бинарного поиска) до последнего совпадения
Зачем бегать по массиву с бинарным поиском, если можно бегать без бинарного? Частоту ведь нужно посчитать для каждого числа, что и так можно сделать, пройдясь слева направо по отсортированному массиву.

> Если учесть, что данные отсортированы, и выкинуть ненужную хеш-таблицу, еще быстрей будет.

не спорю, зная что данные отсортированны - все решается просто

Естественно, он будет жрать память: там же используются связанные списки + динамический массив. В общем, имеем кучу указателей, указателей на указатели и указателей на указатели на указатели. Да еще и наверняка realloc периодически вылезает...

Тогда вообще халява же получается!

но и ты не прав :) с уточненного условия ТС вообще нафиг не нужен lower_bound, обычный цикл

Однократный цикл, выделяем массив, скажем на 1024 элемента и начинаем заполнять. Если не хватает - делаем ему realloc, либо выделяем доп. массив. И так далее.

спасибо за ответы.
можно псевдокодом (а то код будет на языке похожем на бейсик :-)) окончательный вариант алгоритма?

Спасибо!

да, не прав, достаточно посмотреть что делает unique, чуть поправить, и ответ готов ;)

Предположим, что у тебя есть упорядоченный список чисел и ты хочешь получить список пар (число . количество его вхождений в список). Тогда на псевдокоде получим.

(дефун листвгист (источник приёмник)
   (Когда (пуст источник) приёмник
          (если
              ((совпадает (первый элемент источника) (последний элемент приёмника)) (листвгист (откусить голову источнику) (+1 к вхождению числа в приёмник)))
              (иначе (листвгист (откусить голову источнику) (добавить элемент списка к приёмнику, установив число его вхождений в список равным единице)))))

typedef struct _pt{
  int idx;
  int num;
  struct _pt *next;
} pt;

// elements[len] - наш отсортированный массив
pt *first, *current;
int lastval
first = malloc(sizeof(pt));
first->idx = lastval = elements[0];
first->num = 1;
current = first;
for(int i = 1; i < len; i++){
  if(elements[i] == lastval){
    current->num++;
    continue;
  }
  current->next = malloc(sizeof(pt));
  current = current->next;
  current->idx = lastval = elements[i];
  current->num = 1;
}

Получаем связанный список {значение, количество}.

> map<float

Никогда так не делай

спасибо!

то есть получается, что для данной задачи очевидный алгоритм является наилучшим...

А не будет ли забавным такой способ:

Проверить первый и последний элементы на равенство. Если они равны, то,собственно, получили, частоту вхождения в массив.

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

Если в массиве есть достаточно длинные серии, такой способ может быть более смешным.

> Если в массиве есть достаточно длинные серии, такой способ может быть более смешным.

а если нет - то более медленным, при том куда менее читабельным

Что?

Рекурсия всегда понятнее итераций.

> Что?

Рекурсия всегда понятнее итераций.

напиши сюда код на С, и я напишу - сравним, ок?

лучше сделать как в задаче про два яйца и 100 этажей, тогда сложность будет O(sqrt(n))

И что здесь может быть непонятного?

Сравнивай

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

Какие, нафиг, пляски - это абсолютно тот же алгоритм, что и по ссылке

Можно оформить выделение элемента как отдельную функцию - код от этого только жирнее станет

Сравнивай

как скажешь:

для всех элементов в data
   если элемент первый или не совпадает с предыдущим
      добавляем новую пару, устанавливаем значение в 1
   иначе
      для текущей пары увеличиваем значение на 1

да - нет скобочек, но думаю разберешься

можно даже разместить рядом для наглядности:

(дефун листвгист (источник приёмник)
   (Когда (пуст источник) приёмник
          (если
              ((совпадает (первый элемент источника) (последний элемент приёмника)) (листвгист (откусить голову источнику) (+1 к вхождению числа в приёмник)))
              (иначе (листвгист (откусить голову источнику) (добавить элемент списка к приёмнику, установив число его вхождений в список равным единице)))))

для всех элементов
   если элемент первый или не совпадает с предыдущим
      добавляем новую пару, устанавливаем значение в 1
   иначе
      для текущей пары увеличиваем значение на 1

current->next = malloc(sizeof(pt));

malloc(sizeof(pt)) --- мало относится к задаче, и сильно относится к памяти.

еще более весело, что на С++ код будет еще меньше чем описание, а на лиспе - вероятно больше чем его описание

Ну, да. Свёртка списков примитивно отображается на рекурсию, как и наоборот.

P.S. Коммон Лисп --- пользуйтесь уже сейчас тем, что индустрия откроет для себя только лет через тридцать.

А без этого - никуда :)

> Ну, да. Свёртка списков примитивно отображается на рекурсию, как и наоборот.

речь шла про читабельность

кстати, как этот псевдокод будет выглядеть на лиспе или схеме?

вот кстати на С++ вариант, чтоб потом сравнить:

for( size_t i = 0 ; i < count ; ++i )
{
    if( !i || data[ i ] != data[ i - 1 ] )
        res.push_back( data[ i ] );
    else
        res.back().count++;
}

res - соотв-но вектор структур из двух полей, можно даже стандартный pair взять, если лень добавлять структуру

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import absolute_import, division, print_function, unicode_literals

import random
import math
import time

def main():
    arr_size = 1000000
    # generate
    arr = []
    for i in xrange(0, arr_size):
        arr.append(round(random.gauss(5, 0.85), 0))
    arr.sort()
    #print('array:')
    #print(arr)
    # O(n)
    t1 = time.time()
    frq0 = {}
    for i in arr:
        if i in frq0:
            frq0[i] += 1
        else:
            frq0[i] = 1
    t2 = time.time()
    print('frq O(n):')
    print(sorted(frq0.iteritems()))
    print('time: %.3f' % (t2 - t1))
    # O(sqrt(n))
    t1 = time.time()
    frq = {}
    left_k = 0
    while left_k < arr_size:
        left_v = arr[left_k]
        width = arr_size - 1 - left_k
        step = int(math.sqrt(width))
        step = step if step else 1
        big_probe = left_k
        big_probe += step
        while big_probe < arr_size:
            if arr[big_probe] != left_v:
                break
            big_probe += step
        small_probe = big_probe - step
        while small_probe < arr_size:
            if arr[small_probe] != left_v:
                break
            small_probe += 1
        frq[left_v] = (small_probe - left_k)
        if left_k == small_probe:
            print('// hm...')
            break
        left_k = small_probe
    t2 = time.time()
    print('frq O(sqrt(n)):')
    print(sorted(frq.iteritems()))
    print('time: %.3f' % (t2 - t1))

if __name__ == '__main__':
    main()

результат:

frq O(n):
[(1.0, 24), (2.0, 1554), (3.0, 36812), (4.0, 238640), (5.0, 444636), (6.0, 239592), (7.0, 37104), (8.0, 1611), (9.0, 27)]
time: 0.679
frq O(sqrt(n)):
[(1.0, 24), (2.0, 1554), (3.0, 36812), (4.0, 238640), (5.0, 444636), (6.0, 239592), (7.0, 37104), (8.0, 1611), (9.0, 27)]
time: 0.002

значения подогнаны под решение, достаточно заменить round(random.gauss(5, 0.85), 0) на i, и:

frq O(n):
time: 0.141
frq O(sqrt(n)):
time: 1.279