-1

このようにフォーマットされた5,000,000の順序付けられていない文字列があります（Name.Name.Day-Month-Year 24hrTime）：

"John.Howard.12-11-2020 13:14"
"Diane.Barry.29-07-2020 20:50"
"Joseph.Ferns.08-05-2020 08:02"
"Joseph.Ferns.02-03-2020 05:09"
"Josephine.Fernie.01-01-2020 07:20"
"Alex.Alexander.06-06-2020 10:10"
"Howard.Jennings.07-07-2020 13:17"
"Hannah.Johnson.08-08-2020 00:49"
...

n と m の間の時間 t を持つすべての文字列を見つける最速の方法は何ですか? (つまり、時間 < n || m < 時間のすべての文字列を削除する最速の方法)

このフィルタリングは、異なる範囲で複数回行われます。時間範囲は常に同じ日にする必要があり、開始時刻は常に終了時刻よりも早くなります。

Java では、文字列 M と N と 500 万の文字列リストが与えられた場合の私の現在のアプローチは次のとおりです。

ArrayList<String> finalSolution = new ArrayList<>();

String[] startingMtimeArr = m.split(":");
String[] startingNtimeArr = n.split(":");
Integer startingMhour = Integer.parseInt(startingMtimeArr[0]);
Integer startingMminute = Integer.parseInt(startingMtimeArr[1]);
Integer endingNhour = Integer.parseInt(startingNtimeArr[0]);
Integer endingNminute = Integer.parseInt(startingNtimeArr[1]);

for combinedString in ArraySizeOf5Million{
  String[] arr = combinedString.split(".");
  String[] subArr = arr[2].split(" ");
  String[] timeArr = subArr[1].split(":");
  String hour = timeArr[0];
  String minute = timeArr[1];

   If hour >= startingMhour 
        && minute >= startingMminute 
        && hour <= endingNhour 
        && minute <= endingNminute {
    finalSolution.add(hour)
   } 
}

Java は私の母国語ですが、他の言語でも機能します。より良い/より速いロジックが私が求めているものです

4

3 に答える 3

0

1 分ごとにインデックスを使用する Python の例:

from pprint import pprint
from itertools import groupby

big_list = [
    "John.Howard.12:14",
    "Diane.Barry.13:50",
    "xxxDiane.Barryxxx.13:50",  # <-- added a name in the same HH:MM
    "Joseph.Ferns.08:02",
    "Joseph.Ferns.05:09",
    "Josephine.Fernie.07:20",
    "Alex.Alexander.10:10",
    "Howard.Jennings.12:17",
    "Hannah.Johnson.00:49",
]

# 1. sort the list by time HH:MM
big_list = sorted(big_list, key=lambda k: k[-5:])

# the list is now:

# ['Hannah.Johnson.00:49',
#  'Joseph.Ferns.05:09',
#  'Josephine.Fernie.07:20',
#  'Joseph.Ferns.08:02',
#  'Alex.Alexander.10:10',
#  'John.Howard.12:14',
#  'Howard.Jennings.12:17',
#  'Diane.Barry.13:50',
#  'xxxDiane.Barryxxx.13:50']

# 2. create an index (for every minute in a day)
index = {}

times = []
for i, item in enumerate(big_list):
    times.append(int(item[-5:-3]) * 60 + int(item[-2:]))

last = 0
cnt = 0
for v, g in groupby(times):
    for i in range(last, v):
        index[i] = [cnt, cnt]
    s = sum(1 for _ in g)
    index[v] = [cnt, cnt + s]
    cnt += s
    last = v + 1

for i in range(last, 60 * 24):
    index[i] = [cnt, cnt]


# 3. you can now do a fast query using the index
def find_all_strings(n, m):
    n = int(n[-5:-3]) * 60 + int(n[-2:])
    m = int(m[-5:-3]) * 60 + int(m[-2:])

    return big_list[index[n][0] : index[m][1]]


print(find_all_strings("00:10", "00:30"))  # []
print(find_all_strings("00:30", "00:50"))  # ['Hannah.Johnson.00:49']
print(find_all_strings("12:00", "13:55"))  # ['John.Howard.12:14', 'Howard.Jennings.12:17', 'Diane.Barry.13:50', 'xxxDiane.Barryxxx.13:50']
print(find_all_strings("13:00", "13:55"))  # ['Diane.Barry.13:50', 'xxxDiane.Barryxxx.13:50']
print(find_all_strings("15:00", "23:00"))  # []
于 2021-05-17T00:49:23.603 に答える