最快串滤波算法

Question

我有5,000,000个无序字符串是这样格式化的(Name.Name.Day-月月-年份24 have )：

"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的最快方法是什么？(即以最快的方式删除所有时间

此筛选将在不同的范围内多次进行。时间范围必须总是在同一天，而且开始时间总是早于结束时间。

在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是我的母语，但任何其他语言也能工作。我所追求的是更好/更快的逻辑。

Answer 1

由于数据将被搜索很多次，所以我首先解析字符串以便于多次搜索=见by_date。

我使用二进制搜索来查找特定一天的第一个字符串，然后通过不断增加的次数迭代，在变量filtered of function strings_between中收集适当的字符串。

# -*- coding: utf-8 -*-
"""
https://stackoverflow.com/questions/67562250/fastest-string-filtering-algorithm

Created on Tue May 18 09:20:11 2021

@author: Paddy3118
"""

strings = """\
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
Josephine.Fernie.08-08-2020 07:20
Alex.Alexander.08-08-2020 10:10
Howard.Jennings.08-08-2020 13:17
Hannah.Johnson.08-08-2020 09:49\
"""

## First parse the date information once for all future range calcs

def to_mins(hr_mn='00:00'):
    hr, mn = hr_mn.split(':')
    return int(hr) * 60 + int(mn)


by_date = dict()    # Keys are individual days, values are time-sorted
for s in strings.split('\n'):
    name_day, time = s.strip().split()
    name, day = name_day.rsplit('.', 1)
    minutes = to_mins(time)
    if day not in by_date:
        by_date[day] = [(minutes, s)]
    else:
        by_date[day].append((minutes, s))
for day_info in by_date.values():
    day_info.sort()


## Now rely on dict search for day then binary +linear search within day.

def _bisect_left(a, x):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    'a' is a list of tuples whose first item is assumed sorted and searched apon.
    """

    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if a[mid][0] < x: lo = mid+1
        else: hi = mid
    return lo


def strings_between(day="01-01-2020", start="00:00", finish="23:59"):
    global by_date

    if day not in by_date:
        return []
    day_data = by_date[day]
    start, finish = to_mins(start), to_mins(finish)
    from_index = _bisect_left(day_data, start)

    filtered = []
    for time, s in day_data[from_index:]:
        if time <= finish:
            filtered.append(s)
        else:
            break
    return filtered


## Example data

assert by_date == {
 '12-11-2020': [(794, 'John.Howard.12-11-2020 13:14')],
 '29-07-2020': [(1250, 'Diane.Barry.29-07-2020 20:50')],
 '08-05-2020': [(482, 'Joseph.Ferns.08-05-2020 08:02')],
 '02-03-2020': [(309, 'Joseph.Ferns.02-03-2020 05:09')],
 '01-01-2020': [(440, 'Josephine.Fernie.01-01-2020 07:20')],
 '06-06-2020': [(610, 'Alex.Alexander.06-06-2020 10:10')],
 '07-07-2020': [(797, 'Howard.Jennings.07-07-2020 13:17')],
 '08-08-2020': [(49, 'Hannah.Johnson.08-08-2020 00:49'),
                (440, 'Josephine.Fernie.08-08-2020 07:20'),
                (589, 'Hannah.Johnson.08-08-2020 09:49'),
                (610, 'Alex.Alexander.08-08-2020 10:10'),
                (797, 'Howard.Jennings.08-08-2020 13:17')]}

## Example queries from command line
"""
In [7]: strings_between('08-08-2020')
Out[7]:
['Hannah.Johnson.08-08-2020 00:49',
 'Josephine.Fernie.08-08-2020 07:20',
 'Hannah.Johnson.08-08-2020 09:49',
 'Alex.Alexander.08-08-2020 10:10',
 'Howard.Jennings.08-08-2020 13:17']

In [8]: strings_between('08-08-2020', '09:30', '24:00')
Out[8]:
['Hannah.Johnson.08-08-2020 09:49',
 'Alex.Alexander.08-08-2020 10:10',
 'Howard.Jennings.08-08-2020 13:17']

In [9]: strings_between('08-08-2020', '09:49', '10:10')
Out[9]: ['Hannah.Johnson.08-08-2020 09:49', 'Alex.Alexander.08-08-2020 10:10']

In [10]:
"""

Answer 2

正如@Paddy3118 3118已经指出的那样，二进制搜索可能是前进的道路。

date/time.

• With

1. (如果您的数据在磁盘上)：加载输入数据并按 i0排序作为结果集的开始索引，i1作为结果集的结束索引(都是通过二进制搜索获得的)：枚举结果项。

我使用的代码(在Lisp中)显示在这个答案的末尾。它一点也不优化(我想，通过一些优化工作，可以使加载和初始排序变得更快)。

这就是我的交互式会话的样子(包括时间信息，用于包含500万条目的foo.txt输入文件)。

sbcl -动态空间大小2048

这是SBCL 2.1.1.debian，ANSI的一个实现。有关SBCL的更多信息可在http://www.sbcl.org/上获得。SBCL是免费软件，按原样提供，绝对没有保修。它主要是在公共领域；一些部分是在BSD风格的许可下提供的。有关更多信息，请参见发行版中的学分和复制文件。

(ql:quickload :cl)

加载"cl-ppcre"：

负载1 ASDF系统：

克莱普雷

装货"cl-ppcre“

。。

(CL-PPCRE)

(load "fivemillion.lisp")

T

( data (负载输入查询“foo.txt”))

“分类.”

评价结果如下：

32.091秒实时

32.090620秒的总运行时间(31.386722用户，0.703898系统)

运行时间包括2.641秒GC时间和29.450秒非GC时间.

100.00% CPU

15只羔羊

115,308,171,684处理器周期

6,088,198,752字节

数据

(时间( (query-interval output data '(2018 1) '(2018 12)

评价结果如下：

0.000秒实时

0.000111秒的总运行时间(0.000109用户，0.000002系统)

100.00% CPU

395,172处理器周期

65,536字节

输出

(时间( (query-interval output data '(2018 1) '(2018 1 2 8)

评价结果如下：

0.000秒实时

0.000113秒的总运行时间(0.000110用户，0.000003系统)

100.00% CPU

399,420处理器周期

65,536字节

输出

(时间( (query-interval output data '(2018 1 1) '(2019 1 1)

评价结果如下：

0.020秒实时

0.022469秒的总运行时间(0.022469用户，0.000000系统)

110.00% CPU

80,800,092处理器周期

15,958,016字节

输出

因此，虽然加载和排序时间(只完成一次)没有什么好写的(但可以进行优化)，但是(query-interval ...)调用非常快。查询的结果集越大，函数返回的列表就越长(越多的会话，越多的运行时间)。我本来可以更聪明，只需返回结果集的开始和结束索引，并将条目的收集留给调用者。

这里是源代码，它还包括生成我使用的测试数据集的代码：

(defun random-uppercase-character ()
  (code-char (+ (char-code #\A) (random 26))))
(defun random-lowercase-character ()
  (code-char (+ (char-code #\a) (random 26))))
(defun random-name-part (nchars)
  (with-output-to-string (stream)
    (write-char (random-uppercase-character) stream)
    (loop repeat (- nchars 1) do
      (write-char (random-lowercase-character) stream))))
(defun random-day-of-month ()
  "Assumes every month has 31 days, because it does not matter
for this exercise."
  (+ 1 (random 31)))
(defun random-month-of-year ()
  (+ 1 (random 12)))
(defun random-year ()
  "Some year between 2017 and 2022"
  (+ 2017 (random 5)))
(defun random-hour-of-day ()
  (random 24))
(defun random-minute-of-hour ()
  (random 60))
(defun random-entry (stream)
  (format stream "\"~a.~a.~d-~d-~d ~d:~d\"~%"
      (random-name-part 10)
      (random-name-part 10)
      (random-day-of-month)
      (random-month-of-year)
      (random-year)
      (random-hour-of-day)
      (random-minute-of-hour)))
(defun generate-input (entry-count file-name)
  (with-open-file (stream
           file-name
           :direction :output
           :if-exists :supersede)
    (loop repeat entry-count do
      (random-entry stream))))

(defparameter *line-scanner*
  (ppcre:create-scanner
   "\"(\\w+).(\\w+).(\\d+)-(\\d+)-(\\d+)\\s(\\d+):(\\d+)\""))
;;      0       1      2      3      4        5      6
;;      fname   lname  day    month  year     hour   minute

(defun decompose-line (line)
  (let ((parts (nth-value
        1
        (ppcre:scan-to-strings
         *line-scanner*
         line))))
    (make-array 7 :initial-contents
        (list (aref parts 0)
              (aref parts 1)
              (parse-integer (aref parts 2))
              (parse-integer (aref parts 3))
              (parse-integer (aref parts 4))
              (parse-integer (aref parts 5))
              (parse-integer (aref parts 6))))))
(defconstant +fname-index+ 0)
(defconstant +lname-index+ 1)
(defconstant +day-index+ 2)
(defconstant +month-index+ 3)
(defconstant +year-index+ 4)
(defconstant +hour-index+ 5)
(defconstant +minute-index+ 6)
(defvar *compare-<-criteria*
  (make-array 5 :initial-contents
          (list +year-index+
            +month-index+
            +day-index+
            +hour-index+
            +minute-index+)))

(defun compare-< (dl1 dl2)
  (labels ((comp (i)
         (if (= i 5)
         nil
         (let ((index (aref *compare-<-criteria* i)))
           (let ((v1 (aref dl1 index))
             (v2 (aref dl2 index)))
             (cond
               ((< v1 v2) t)
               ((= v1 v2) (comp (+ i 1)))
               (t nil)))))))
    (comp 0)))
           
(defun time-stamp-to-index (hours minutes)
  (+ minutes (* 60 hours)))

(defun load-input-for-queries (file-name)
  (let* ((decomposed-line-list
       (with-open-file (stream file-name :direction :input)
         (loop for line = (read-line stream nil nil)
           while line
           collect (decompose-line line))))
     (number-of-lines (length decomposed-line-list))
     (decomposed-line-array (make-array number-of-lines
                        :initial-contents
                        decomposed-line-list)))
    (print "sorting...") (terpri)
    (sort decomposed-line-array #'compare-<)))

(defun unify-date-list (date)
  (let ((date-length (length date)))
    (loop
      for i below 5
      collecting (if (> date-length i) (nth i date) 0))))

(defun decomposed-line-date<date-list (decomposed-line date-list)
  (labels ((comp (i)
         (if (= i 5)
         nil
         (let ((index (aref *compare-<-criteria* i)))
           (let ((v1 (aref decomposed-line index))
             (v2 (nth i date-list)))
             (cond
               ((< v1 v2) t)
               ((= v1 v2) (comp (+ i 1)))
               (t nil)))))))
    (comp 0)))

(defun index-before (data key predicate
             &key (left 0) (right (length data)))
  (if (and (< left right) (> (- right left) 1))
      (if (funcall predicate (aref data left) key)
      (let ((mid (+ left (floor (- right left) 2))))
        (if (funcall predicate (aref data mid) key)
        (index-before data key predicate
                  :left mid
                  :right right)
        (index-before data key predicate
                  :left left
                  :right mid)))
      left)
      right))

(defun query-interval (data start-date end-date)
  "start-date and end-date are given as lists of the form:
'(year month day hour minute) or shorter versions e.g.
'(year month day hour), omitting trailing values which will be
appropriately defaulted."
  (let ((d0 (unify-date-list start-date))
    (d1 (unify-date-list end-date)))
    (let* ((start-index (index-before
             data
             d0
             #'decomposed-line-date<date-list))
       (end-index (index-before
               data
               d1
               #'decomposed-line-date<date-list
               :left (cond
                   ((< start-index 0) 0)
                   ((>= start-index (length data))
                (length data))
                   (t start-index)))))
      (loop for i from start-index below end-index
        collecting (aref data i)))))