0

好吧不确定是否有比我已经在做的更好的方法。现在我有一个列表（int []），其中有超过 10,000 个等于 0 的值，我只寻找非零项。

我目前的方法只是做一个 for 循环并捕获所有非零值，但我经常这样做，并且分析显示它占用了我大量的 cpu 时间（因为我经常这样做）。有没有一种方法可以在没有昂贵的 cpu 进程的情况下获得相同的结果（因为有 10,000 个项目，只有不到 100 个是非零的）？

这是我的数据示例：

int[] list = {0,0,0,1,0,10 }
int[] list_names = {a,b,c,d,e,f}

我最终需要做的就是使用这两个列表创建另外两个列表，其中只有非零值及其名称（因此 D=1 和 F=10）。我已经看到了一些解决方案，我需要在结果工作之前对其进行排序，但这是一个问题，因为如果我对数据列表进行排序，那么我无法识别它的名称。

这可能吗？与 for 循环相比，有没有更快的方法？

抱歉，我应该提一下，这个大列表仍在我的程序中进行处理，我正在尝试这样做以减少它们的内存占用。当我真正需要的是非零值时，我有一个包含几亿个这些列表的队列被完整存储，所以这样做是为了节省内存（这似乎是有效的），但我也尽量不这样做对 cpu 进行一点打击以使其达到这一点（因为我需要 cpu 进行处理）。

4

6 回答 6

3

如果您对数组一无所知，那么您将不得不查看每个值。这意味着循环整个数组基本上是您所希望的最好的。如果它已排序，或者如果您知道有关它的一些其他信息，那可能会有所帮助——但除此之外，别无选择。

于 2012-04-12T01:28:28.617 回答
1

是否可以预先对列表进行排序，以便更容易找到非零？这个想法是预排序一次或插入新数据时。因此，检索已经排序并且很容易。

编辑：

然后使用表的哈希码。如果哈希码没有改变，那么您不需要搜索列表/表格。

于 2012-04-12T01:26:28.160 回答
1

如果您阅读的频率高于写作频率，您可以缓存搜索结果。创建一个非零项目列表，并将其保留在那里直到下一次写入。

您还可以将一组所有索引保留到值不为零的原始数组中。每次将列表中的值更改为零时，从集合中删除该值的索引；每次将值设置为非零时，将其索引添加到集合中。这种方式而不是搜索非零条目，您只需从一组已知索引中获取。

于 2012-04-12T01:28:28.160 回答
1

如果你得到的只是一个未排序的整数数组，那么如果不查看所有元素就不可能做到这一点。

另请注意，排序本身比 O(n) 差，因此排序对您没有帮助。

如果您之后以某种方式操作这些数组，那么生成可以使用的稀疏表示（如索引到值的映射）将是有意义的。

如果不知道更多，很难说你能做什么，也许有一些机会通过在多个线程中做一些工作来加快速度？

于 2012-04-12T01:34:33.527 回答
1

记住您找到非零值的位置。将索引和值分别存储在单独的数组中。

所以0, 2, 0, 1, 0, 7变成

int[] list_index = {1,3,5}
int[] list_value = {2,1,7}

然后遍历数组中的值list_index作为索引names并存储相应的list_value.

于 2012-04-12T01:36:01.823 回答
1

与其拥有一个List<Integer>具有零值和非零值的大值，不如保留一个List<Integer>甚至是一个计数器数组，在此列表中，您只会有多少次将一个数字放入其中。

public class MyList {

    private final int MAX_SIZE = 1001;
    private int[] myList;
    private int size;

    public MyList() {
        this.size= MAX_SIZE;
        this.myList = new int[size];
    }

    public MyList(int maxSize) {
        this.size = maxSize;
        this.myList = new int[size];
    }

    public boolean add(int e) {
        if (e < 0 || (e > size - 1))
            return false;
        this.myList[e]++;
        return true;
    }

    public void remove(int e) {
        if (e < 0 || (e > size - 1))
            return;
        if (this.myList[e] > 0)
            this.myList[e]--;
    }

    public int getTimes(int number) {
        if (number < 0 || (number > size - 1))
            return 0;
        return this.myList[number];
    }
}
于 2012-04-12T01:42:09.283 回答