相关疑难解决方法(0)

我的一个朋友被问到一个问题

从一亿个数字中检索最大前100个数字

在最近的一次面试中.你有什么想法想出一个有效的解决方法吗？

我最近在面试期间进行了编码测试。有人告诉我：

有一个一百万个的大型未排序数组int。用户想要检索K最大的元素。你会实现什么算法？

在此期间，我强烈暗示我需要对数组进行排序。

因此，如果性能确实很重要，我建议使用内置sort()或自定义实现。然后我被告知，使用Collectionor数组来存储k最大的元素和 for 循环可以实现大约O(N)，事后看来，我认为这是O(N*k)因为每次迭代都需要与大小数组进行比较K以找到要替换的最小元素，而需要对数组进行排序将导致代码至少为O(N log N).

然后我回顾了 SO 上的这个链接，它建议K数字的优先级队列，每次找到较大的元素时删除最小的数字，这也会给出O(N log N). 编写一个程序，从 10 亿个数字的数组中找出 100 个最大的数字

for循环方法不好吗？我应该如何证明使用 for 循环或优先级队列/排序方法的优点/缺点？我认为，如果数组已经排序，则不需要再次迭代整个数组，即如果对排序数组调用其他检索方法，则它应该是恒定时间。运行实际代码时是否存在一些我在理论化伪代码时没有考虑到的性能因素？

我有一个有100万个数字的文件.我需要知道如何有效地对它进行排序,这样它就不会使计算机失速,并且它只打印前10名.

#!/usr/bin/python3

#Find the 10 largest integers
#Don't store the whole list

import sys

def fOpen(fname):
        try:
                fd = open(fname,"r")
        except:
                print("Couldn't open file.")
                sys.exit(0)
        all = fd.read().splitlines()
        fd.close()
        return all

words = fOpen(sys.argv[1])

big = 0
g = len(words)
count = 10

for i in range(0,g-1):
        pos = i
        for j in range(i+1,g):
                if words[j] > words[pos]:
                        pos = j
                if pos != i:
                        words[i],words[pos] = words[pos],words[i]
                count -= 1
                if count == 0:
                        print(words[0:10])

我知道这是选择排序,我不确定什么是最好的选择.

问题:我经常需要查看特定日志最后一天内最常重复的"模式".就像这里的一小部分tomcat日志一样:

GET /app1/public/pkg_e/v3/555413242345562/account/stats 401 954 5
GET /app1/public/pkg_e/v3/555412562561928/account/stats 200 954 97
GET /app1/secure/pkg_e/v3/555416251626403/ex/items/ 200 517 18
GET /app1/secure/pkg_e/v3/555412564516032/ex/cycle/items 200 32839 50
DELETE /app1/internal/pkg_e/v3/accounts/555411543532089/devices/bbbbbbbb-cccc-2000-dddd-43a8eabcdaa0 404 - 1
GET /app1/secure/pkg_e/v3/555412465246556/sessions 200 947 40
GET /app1/public/pkg_e/v3/555416264256223/account/stats 401 954 4
GET /app2/provisioning/v3/555412562561928/devices 200 1643 65
...

如果我想找出最常用的URL(以及方法和重新编码) - 我会这样做:

[root@srv112:~]$ N=6;cat test|awk '{print $1" "$2" ("$3")"}'\
|sed 's/[0-9a-f-]\+ (/%GUID% (/;s/\/[0-9]\{4,\}\//\/%USERNAME%\//'\
|sort|uniq -c|sort -rn|head -$N
      4 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (401)
      2 GET /app1/secure/pkg_e/v3/%USERNAME%/devices (200)
      2 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (200)
      2 DELETE /app1/internal/pkg_e/v3/accounts/%USERNAME%/devices/%GUID% (404)
      1 POST /app2/servlet/handler …

IntStream可能是最简单的方法,但我只能选择最小的M数字,如下所示:

public class Test {
    private static final int[] arr = {5, 3, 4, 2, 9, 1, 7, 8, 6};

    public static void main(String[] args) throws Exception {
        System.out.println(Arrays.asList(IntStream.of(arr).sorted().limit(5).boxed().toArray()));
    }
}

顺便说一句,考虑到算法的复杂性并假设N >> M,"排序+限制"方法只有O(N log(N))的复杂度.

我认为最好的复杂性可能达到O(N log(M)),但我不知道Java 8是否有这种流方法或收集器.