|
|
Рискуя навлечь на себя гнев конференции, хотел бы вновь вернутся к теме
поиска наиболее часто встречающегося значения:
http://telesys.ru/wwwboards/mcontrol/1171/messages/161460.shtml
Алгоритм, предложенный DASM'ом:
http://telesys.ru/wwwboards/mcontrol/1171/messages/161504.shtml
требует при SIZE = 10
Число_проходов_внутреннего_цикла = 10*256 = 2560
и не требует памяти для хранения гистограммы.
При использовании переменных типа "short":
Число_проходов_внутреннего_цикла = 10*65536 = 655360.
Само тело цикла достаточно короткое.
Оценка производительности предлагаемого ниже алгоритма:
SIZE < = Число_проходов_внутреннего_цикла < = SIZE*SIZE/2
Те, для SIZE = 10:
10 < = Число_проходов_внутреннего_цикла < = 50
Первое неравенство соответствует случаю, когда все числа в массиве равны.
Второе неравенство соответствует случаю, когда все числа в массиве различны.
Требуется память для хранения самой гистограммы (freq[SIZE]).
Если допускается разрушение входного массива (#define INPLACE),
то значения величин, соответствующих элементам гистограммы
можно хранить во входном массиве (src[SIZE]).
Иначе, необходим отдельный массив (dst[SIZE]).
Тело цикла несколько длиннее чем у DASM'а.
Вот текст программы:
// Gistogram.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#define INPLACE
#define SIZE 32
int src[SIZE] =
{
7,7,7,
2,2,
5,5,5,5,5,
7,7,7,7,
1,
9,9,
4,4,4,4,
9,9,9,
3,3,3,
9,9,9,9,
0
};
int freq[SIZE] = {0};
#ifdef INPLACE
#define dst src
#else
int dst[SIZE];
#endif
int _tmain(int argc, _TCHAR* argv[])
{
int i,j,k;
int max,val;
k = 0;
max = 0;
for (i = 0; i < SIZE; i++)
{
for (j = 0; j < k; j++)
{
if(dst[j] == src[i])
{
freq[j]++;
if (max < freq[j])
{
val = src[i];
max = freq[j];
};
goto scan;
}
}
dst[k] = src[i];
freq[k] = 1;
k++;
scan:
continue;
}
printf("Gistogram:\n");
printf("Value\tTimes\n");
for (j = 0; j < k; j++) printf("%d\t%d\n",dst[j],freq[j]);
printf("The most frequent number is %d.\nFound %d times.",val,max);
return 0;
}
|
|
E-mail: 
info@telesys.ru
