2

最大/最小オカレンスを持つ入力整数配列で値を見つけるアルゴリズムを書き終えました。私の考えは、配列をソートし（すべての出現が順番になっています）、<value:occurrences>ペアを使用してすべての値に対応する出現数を格納することです。

複雑なはずですO(nlogn)が、一定の乗数があると思います。パフォーマンスを向上させるにはどうすればよいですか?

#include <stdio.h>
#include <stdlib.h>
#include "e7_8.h"

#define N 20
/*Structure for <value, frequencies_count> pair*/
typedef struct {
    int value;
    int freq;
} VAL_FREQ;


void  get_freq(int *v, int n, int *most_freq, int *less_freq) {

    int v_i, vf_i, current_value, current_freq;

    VAL_FREQ* sp = malloc(n*sizeof(VAL_FREQ));
    if(sp == NULL) exit(EXIT_FAILURE);

    mergesort(v,n);

    vf_i = 0;
    current_value = v[0];
    current_freq = 1;
    for(v_i=1; v_i<n+1; v_i++) {
        if(v[v_i] == current_value) current_freq++;
        else{
            sp[vf_i].value = current_value;
            sp[vf_i++].freq = current_freq;
            current_value = v[v_i];
            current_freq = 1;
        }
    }
    /*Finding max,min frequency*/
    int i, max_freq_val, max_freq, min_freq_val, min_freq;

    max_freq = sp[0].freq;
    max_freq_val = sp[0].value;
    min_freq = sp[0].freq;
    min_freq_val = sp[0].value;
    for(i=1; i<vf_i; i++) {
        if(sp[i].freq > max_freq) {
            max_freq = sp[i].freq;
            max_freq_val = sp[i].value;
        }
        if(sp[i].freq < min_freq) {
            min_freq = sp[i].freq;
            min_freq_val = sp[i].value;
        }
    }

    *most_freq = max_freq_val;
    *less_freq = min_freq_val;

    free(sp);
}
4

2 に答える 2

5

ハッシュ テーブルを使用してキーと値のマップを実装しますか? これにより、O(n) の予想時間が得られるはずです。*

※但し、最悪の場合O(n 2 )であることに注意。これは、すべてのエントリが同じバケットにハッシュされ、反復ごとにリンクされたリストを効果的に検索する場合にのみ発生します! まともなハッシュテーブルの実装では、これが発生する可能性は非常に低いです。

于 2013-06-25T20:41:13.837 に答える
4

すべてのステップが O(n*log(n)) である並べ替えから離れて O(n) であるため、アルゴリズムが既に O(n*log(n)) であるという事実から始めましょう。大幅に改善できるかどうかは、期待する入力の種類によって異なります。編集：そうでない限り、プロセスの最後に値をソートする要件の一部ではありません（いずれにしても、発生数ではなく値で）。その場合、Oliを見逃すことはありませんチャールズワースの答え。

地上には 2 つの概念があります。1 つ目は、取得するサンプルの数 (n) です。2 つ目は、それらの値が「どの程度集中しているか」、これらの値を分散できる範囲がどの程度狭いか広いか (w = MAX_VALUE - MIN_VALUE) です。

n が w より小さい場合 (値がまばらである場合)、アプローチはすでに最適であり、改善の余地はほとんどありません。

しかし、w が小さく、n が大きい場合は、次の方法で多くのことを得ることができます。

MIN_VALUE 未満の値は取得できず、MAX_VALUE を超える値は取得できないことがわかっているとします。次に、頻度を収集する配列のインデックスとして value を使用できます。このようにして、並べ替えステップ (O(n*log(n)) ) をスキップし、O(n) で頻度を計算します。

int buffer_frequencies[MAX_VALUE - MIN_VALUE + 1];

//Now reset the array with some convenient function like memset

int* value_frequencies = buffer_frequencies;
value_frequencies -= MIN_VALUE; //Shift the beginning of the array, so that 
                                //you can use the value directly as the array index
//You are allowed to use negative indexes
for(v_i=0; v_i < n; v_i++) {
  value_frequencies[v[v_i]]++;
  }

または（おそらく for サイクルのわずかに高速なバージョンですが、通常、優れたコンパイラはすでに最も効率的なバージョンに変換しています）：

int* p_v = v;
int* end_p_v = v+n;
for(; p_v < end_p_v; p_v++) {
  value_frequencies[*p_v]++;
  }

このメソッド (両方のバージョン) は入力値に対して非常にデリケートであることに注意してください。つまり、MIN_VALUE または MAX_VALUE を超える値を取得すると、メモリ境界が壊れます。

次に、アルゴリズムの 2 番目の部分:

//First cycle could be optimized, but it has no impact
int i = MIN_VALUE;
max_freq = value_frequencies[i];
max_freq_val = i;
min_freq = value_frequencies[i];
min_freq_val = i;
for(; i<MAX_VALUE; i++) {
    max_freq_val = (value_frequencies[i] > max_freq) ? i : max_freq_val;
    max_freq = (value_frequencies[i] > max_freq) ? value_frequencies[i] : max_freq;
    min_freq_val = (value_frequencies[i] < min_freq) ? i : min_freq_val;
    min_freq = (value_frequencies[i] < min_freq) ? value_frequencies[i] : min_freq;
    }
}
于 2013-06-25T21:05:20.510 に答える