0

私は数字の行を含む大きな配列を持つアプリケーションに取り組んでいます、

transNum[20000][200]//this is the 2d array containing the numbers and always keep track of the line numbers

ネストされたループを使用して、最も頻繁なアイテムを探しています。これは

for(int i=0/*,lineitems=0*/;i<lineCounter;i++)
  {
      for(int j=0,shows=1;j<lineitem1[i];j++)
      {
          for(int t=i+1;t<lineCounter;t++)
          {
              for(int s=0;s<lineitem1[t];s++)
              {
                  if(transNum[i][j]==transNum[t][s])
                      shows++;
              }
          }

          if(shows/lineCounter>=0.2)
          {

              freItem[i][lineitem2[i]]=transNum[i][j];
              lineitem2[i]++;
          }
      }

  }

test [200] [200]のような小さな入力配列を使用してテストを行っていた場合、このループは正常に機能し、計算時間は許容範囲内ですが、配列に12000行が含まれている場合、計算時間が長すぎるため、このループを使用するのではなく、頻繁なアイテムを計算する他の方法があるかどうかを考えています.10688行でテストを実行したところ、すべての頻繁なアイテムを取得する時間は825805msであり、これは非常に高価です。

4

4 に答える 4

1

これはせいぜいO（n ^ 2）アルゴリズムであり、さらに悪い可能性があることに注意してください。つまり、操作の数は、アイテムの2乗の数に比例します。特定の行数を超えると、パフォーマンスが急速に低下し、アルゴリズムを改善する以外にできることはありません。

于 2010-10-02T19:02:51.380 に答える
0

このような場合、GoogleGuavaプロジェクトのマルチセット実装が役立つ可能性があります。そこにアイテムを保存してから、発生するたびにカウントされた値のセットを取得できます。

于 2010-10-02T19:34:30.880 に答える
0

入力によって異なります。同じコードにデータを挿入する場合は、挿入するときに頻繁なアイテムを数えることができます。

疑似Cソリューションは次のとおりです。

int counts[1000000];

while(each number as n)
{
    counts[n]++;
    // then insert number into array
}

編集＃2：予期しない結果が得られないように、配列内のすべての項目をゼロに初期化するようにしてください。

于 2010-10-02T18:46:17.973 に答える
0

これのアルゴリズムにいくつかの考えを与えました。これが私が思いついた解決策です：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class NumberTotalizerTest {

    public static void main(String args[]) {

        HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();

        // Number input
        Random randomGenerator = new Random();
        for (int i = 1; i <= 50; ++i ) {
            int randomInt = randomGenerator.nextInt(15);
            System.out.println("Generated : " + randomInt);

            Integer tempInt = hashMap.get(randomInt);

            // Counting takes place here
            hashMap.put(randomInt, tempInt==null?1:(tempInt+1) );
        }

        // Sorting and display
        Iterator itr =  sortByValue(hashMap).iterator();

        System.out.println( "Occurences from lowest to highest:" );

        while(itr.hasNext()){
            int key = (Integer) itr.next();

            System.out.println( "Number: " + key + ", occurences: " + hashMap.get(key));
        }
    }

     public static List sortByValue(final Map m) {
        List keys = new ArrayList();
        keys.addAll(m.keySet());
        Collections.sort(keys, new Comparator() {
            public int compare(Object o1, Object o2) {
                Object v1 = m.get(o1);
                Object v2 = m.get(o2);
                if (v1 == null) {
                    return (v2 == null) ? 0 : 1;
                }
                else if (v1 instanceof Comparable) {
                    return ((Comparable) v1).compareTo(v2);
                }
                else {
                    return 0;
                }
            }
        });
        return keys;
    }
}
于 2011-01-14T08:09:23.763 に答える