java - 对于大数据量，什么数据结构更快？

Question

我正在开发一个关于 Spring Boot 的项目，并且必须处理存储在 Solr 中的大量信息。我必须将所有存储的图像与用户输入的图像进行比较并建立相似性。我一开始使用图像的 LinkedList，现在使用数组和 LinkedList，但速度也很慢，有时甚至不起作用。我说的是我必须处理的 11 000 000 张图像。这是我的代码:

 public LinkedList<Imagen> comparar(Imagen[] lista, Imagen imagen) throws NullPointerException {
    LinkedList<Imagen> resultado = new LinkedList<>();
    for (int i = 0; i < lista.length; i++) {
        if (lista[i].getFacesDetectedQuantity() == imagen.getFacesDetectedQuantity()) {
            lista[i].setSimilitud(3);
        }
        if (herramientas.rangoHue(imagen.getPredominantColor_hue()).equals(herramientas.rangoHue(lista[i].getPredominantColor_hue()))) {
            lista[i].setSimilitud(3);
        }
        if (lista[i].isTransparency() == imagen.isTransparency()) {
            lista[i].setSimilitud(4);
        }
        if (analizar.compareFeature(herramientas.image64ToImage(lista[i].getLarge_thumbnail()), herramientas.image64ToImage(imagen.getLarge_thumbnail())) > 400) {
            lista[i].setSimilitud(3);
        }
        if (analizar.compare_histogram(herramientas.image64ToImage(lista[i].getLarge_thumbnail()), herramientas.image64ToImage(imagen.getLarge_thumbnail())) > 90) {
            lista[i].setSimilitud(3);
        }
        if (lista[i].getSimilitud() > 7) {
            resultado.add(lista[i]);
        }
    }
    return ordenarLista(resultado);
}


public LinkedList<Imagen> ordenarLista(LinkedList<Imagen> lista) {
    LinkedList<Imagen> resultado = new LinkedList<>();
    for (int y = 0; y < lista.size(); y++) {
        Imagen imagen = lista.get(0);
        int posicion = 0;
        for (int x = 0; x < lista.size(); x++) {
            if (lista.get(x).getSimilitud() > imagen.getSimilitud()) {
                imagen = lista.get(x);
                posicion = x;
            }
        }
        resultado.add(imagen);
        lista.remove(posicion);
    }
    return resultado;
}

知道我可以使用什么数据结构来使过程更快。我也在考虑在线程内创建每个比较 if 但也不知道如何做到这一点。谷歌搜索了很多，却什么也没找到。抱歉我的英语不好，谢谢!

我解决了使用 ordenarLista() 方法排序的问题，只是忽略它，并在返回列表之前将此代码添加到我的 comparar() 方法中。

Collections.sort(resultado, new Comparator<Imagen>() {

            @Override
            public int compare(Imagen image1, Imagen image2) {
                return image2.getSimilitud() - image1.getSimilitud();
            }
        });

仍在研究我的算法!

Answer 1

一般来说，在尝试随机优化任何部分之前，请使用 JVisualVM 等监控工具来准确检测昂贵的调用。你必须把努力放在正确的地方。

此外，跟踪第一次大处理(在 ordenarLista() 之前)和第二次大处理(ordenarLista())所花费的时间也应该会有所帮助。

实际上，我注意到一些事情:

1) 很可能是一个问题:comparar() 执行许多重复处理，这些处理在 CPU 方面可能会很昂贵。

看看这两个调用:

if (analizar.compareFeature(herramientas.image64ToImage(lista[i].getLarge_thumbnail()), herramientas.image64ToImage(imagen.getLarge_thumbnail())) > 400) {
    lista[i].setSimilitud(3);
}
if (analizar.compare_histogram(herramientas.image64ToImage(lista[i].getLarge_thumbnail()), herramientas.image64ToImage(imagen.getLarge_thumbnail())) > 90) {
    lista[i].setSimilitud(3);
}

例如，您在每次迭代时调用 4 次 herramientas.image64ToImage()。

这应该在循环之前执行一次:

herramientas.image64ToImage(imagen.getLarge_thumbnail())

但是你在循环中执行了数百万次。 只需将结果存储在循环之前的变量中并在循环中使用即可。 同样的事情:

herramientas.rangoHue(imagen.getPredominantColor_hue()

所有仅依赖于 Imagen imagen 参数的计算都应该在循环之前进行计算，并且永远不要进行计算，以节省数百万次。

2) ordenarLista() 似乎有问题:您在此处硬编码了第一个索引:

Imagen imagen = lista.get(0);

3) ordenarLista() 可能会迭代多次:

lista.size() + lista.size() 
+
lista.size()-1 + lista.size() 
+
lista.size()-2 + lista.size() 
+
...
+ 1 * lista.size() 

想象一下，其中有 1.000.000 元素:

1.000.000 + 1.000.000 
+
999.999  + 1.000.000 
+
999.998  + 1.000.000 
+
...
+ 
1 + 1.000.000 

它赚了数百万......