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 行上进行了测试，得到所有频繁项的时间是 825805 毫秒，这太昂贵了。

4

4 回答 4

1

请记住，这充其量只是一个 O(n^2) 算法，而且可能更糟。这意味着操作的数量与项目的平方数成正比。经过一定数量的行后，性能会迅速下降，除了改进算法外​​，您无能为力。

于 2010-10-02T19:02:51.380 回答
0

Google Guava 项目的Multiset实现在这种情况下可能很有用。您可以将项目存储在那里，然后检索具有每次出现计数的值集。

于 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 回答