gpt4 book ai didi

查找与给定编号最接近的匹配项的 java 方法。在未排序的整数数组中

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:28:21 25 4
gpt4 key购买 nike

我需要有关 Java 程序的帮助,以找出与未排序的整数数组中任何给定整数的最近匹配

我可以就以下方面提出建议吗:

* How to get start off with this?
* Should i first sort the array

谢谢大家

最佳答案

如果您无法对数组进行排序,或者您只对数组排序一次,您可以这样做。

public static int closest1(int find, int... values) {
int closest = values[0];
for(int i: values)
if(Math.abs(closest - find) > Math.abs(i - find))
closest = i;
return closest;
}

这将返回一个最接近的值。如果您正在寻找两个值之间的均等值,您将获得第一个值。


优化版本。

public static int closest2(int find, int... values) {
int closest = values[0];
int distance = Math.abs(closest - find);
for(int i: values) {
int distanceI = Math.abs(i - find);
if(distance > distanceI) {
closest = i;
distance = distanceI;
}
}
return closest;
}

多线程版本

public static int closest3(final int find, final int... values) {
final int procs = Runtime.getRuntime().availableProcessors();
ExecutorService es = Executors.newFixedThreadPool(procs);
List<Future<Integer>> futures = new ArrayList<Future<Integer>>();
final int blockSize = values.length / procs;
for (int i = 0; i < procs; i++) {
final int start = blockSize * i;
final int end = Math.min(blockSize * (i + 1), values.length);
futures.add(es.submit(new Callable<Integer>() {
@Override
public Integer call() throws Exception {
int closest = values[start];
int distance = Math.abs(closest - find);
for (int i = start + 1; i < end; i++) {
int n = values[i];
int distanceI = Math.abs(n - find);
if (distance > distanceI) {
closest = i;
distance = distanceI;
}
}
return closest;
}
}));
}
es.shutdown();
int[] values2 = new int[futures.size()];
try {
for (int i = 0; i < futures.size(); i++)
values2[i] = futures.get(i).get();
return closest2(find, values2);
} catch (Exception e) {
throw new AssertionError(e);
}
}

运行这个测试

Random rand = new Random();
int[] ints = new int[100 * 1000 * 1000];
for (int i = 0; i < ints.length; i++)
ints[i] = rand.nextInt();

for (int i = 0; i < 5; i++) {
long start1 = System.nanoTime();
closest1(i, ints);
long time1 = System.nanoTime() - start1;

long start2 = System.nanoTime();
closest2(i, ints);
long time2 = System.nanoTime() - start2;

long start3 = System.nanoTime();
closest3(i, ints);
long time3 = System.nanoTime() - start3;
System.out.printf("closest1 took %,d ms, closest2 took %,d ms, closest3 took %,d ms %n", time1 / 1000 / 1000, time2 / 1000 / 1000, time3 / 1000 / 1000);
}

对于 1 亿个打印值

closest1 took 623 ms, closest2 took 499 ms, closest3 took 181 ms 
closest1 took 645 ms, closest2 took 497 ms, closest3 took 145 ms
closest1 took 625 ms, closest2 took 495 ms, closest3 took 134 ms
closest1 took 626 ms, closest2 took 494 ms, closest3 took 134 ms
closest1 took 627 ms, closest2 took 495 ms, closest3 took 134 ms

使用第二种方法每百万个条目可节省 0.8 毫秒。第三种方法对于大型阵列要快得多,但对于较小的阵列可能会慢一些。

关于查找与给定编号最接近的匹配项的 java 方法。在未排序的整数数组中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6599371/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com