당신은 당신이 아마 가볍게 내려서 하지 quants 기본 알고리즘을 이해하지 못하는 헤지 펀드에 대한 작동 할 🙂

이 경우처럼 모든 요소를 ​​한 번 이상 방문해야하는 경우 임의 크기의 데이터 구조를 처리 할 수있는 방법 이 없습니다O(1) . 최고의 당신이 희망 할 수있다 O(n)이 경우에 n문자열의 길이입니다.

제쳐두고, 공칭 비록 O(n)알고리즘 할 수 O(1)있으므로, 고정 된 기술적 입력 크기를 들어, 여기에 올바른일지도 모른다. 그러나 이것이 일반적으로 사람들이 복잡성 분석을 사용하는 방식은 아닙니다.

여러 가지 방법으로 그들에게 깊은 인상을 줄 수 있었던 것 같습니다.

먼저 위에서 언급 한 “의심스러운”추론을 사용하지 않는 한에 할 수 없음 을 알리십시오 O(1).

둘째, 다음과 같은 Pythonic 코드를 제공하여 엘리트 기술을 보여줍니다.

inpStr = '123412345123456'

# O(1) array creation.
freq = [0] * 1000

# O(n) string processing.
for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]:
    freq[val] += 1

# O(1) output of relevant array values.
print ([(num, freq[num]) for num in range(1000) if freq[num] > 1])

이 결과는 다음과 같습니다.

[(123, 3), (234, 3), (345, 2)]

물론 출력 형식을 원하는대로 수정할 수 있습니다.

마지막으로, 위의 코드는 0.5 초 안에 100 만 자릿수 문자열에 대한 결과를 제공하기 때문에 솔루션에 아무런 문제가 거의 없다고O(n) 말합니다. 10,000,000 자 문자열은 3.5 초가 걸리고 100,000,000 자 문자열은 36 초가 걸리기 때문에 선형 적으로도 확장되는 것으로 보입니다.

그리고 그것들 이 그보다 더 필요 하다면 , 속도를 크게 높일 수있는 이런 종류의 것들을 병렬화하는 방법이 있습니다.

물론 GIL로 인해 단일 파이썬 인터프리터 내에는 아니지만 문자열을 다음과 같이 나눌 수 있습니다 ( vv경계 영역을 올바르게 처리하려면 겹침이 표시 되어야 함).

    vv
123412  vv
    123451
        5123456

이를 분리하여 작업자를 분리하고 나중에 결과를 결합 할 수 있습니다.

입력 분할과 출력 결합은 작은 문자열 (및 수백만 자릿수의 문자열)로 절약 할 수 있지만 훨씬 더 큰 데이터 세트의 경우 큰 차이가있을 수 있습니다. 물론 “측정, 추측하지 말아”라는 나의 평범한 만트라가 여기에 적용됩니다.

이 만트라는 파이썬을 우회하고 더 빠른 다른 언어를 사용하는 것과 같은 다른 가능성 에도 적용됩니다 .

예를 들어, 다음의 코드 C는 이전 파이썬 코드와 동일한 하드웨어에서 실행하는 처리 백 0.6 초 만 자리 파이썬 코드 처리 시간으로 대략 동일한 양의 하나 백만. 다시 말해, 훨씬 빠릅니다.

#include <stdio.h>
#include <string.h>

int main(void) {
    static char inpStr[100000000+1];
    static int freq[1000];

    // Set up test data.

    memset(inpStr, '1', sizeof(inpStr));
    inpStr[sizeof(inpStr)-1] = '\0';

    // Need at least three digits to do anything useful.

    if (strlen(inpStr) <= 2) return 0;

    // Get initial feed from first two digits, process others.

    int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0';
    char *inpPtr = &(inpStr[2]);
    while (*inpPtr != '\0') {
        // Remove hundreds, add next digit as units, adjust table.

        val = (val % 100) * 10 + *inpPtr++ - '0';
        freq[val]++;
    }

    // Output (relevant part of) table.

    for (int i = 0; i < 1000; ++i)
        if (freq[i] > 1)
            printf("%3d -> %d\n", i, freq[i]);

    return 0;
}

답변

from collections import Counter

def triple_counter(s):
    c = Counter(s[n-3: n] for n in range(3, len(s)))
    for tri, n in c.most_common():
        if n > 1:
            print('%s - %i times.' % (tri, n))
        else:
            break

if __name__ == '__main__':
    import random

    s = ''.join(random.choice('0123456789') for _ in range(1_000_000))
    triple_counter(s)

for nr in range(1000):
    cnt = text.count('%03d' % nr)
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt)

counts = [0] * 1000
for idx in range(len(text)-2):
    counts[int(text[idx:idx+3])] += 1

for nr, cnt in enumerate(counts):
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt)

def setup_data(n):
    import random
    digits = "0123456789"
    return dict(text = ''.join(random.choice(digits) for i in range(n)))

def f_np(text):
    # Get the data into NumPy
    import numpy as np
    a = np.frombuffer(bytes(text, 'utf8'), dtype=np.uint8) - ord('0')
    # Rolling triplets
    a3 = np.lib.stride_tricks.as_strided(a, (3, a.size-2), 2*a.strides)

    bins = np.zeros((10, 10, 10), dtype=int)
    # Next line performs O(n) binning
    np.add.at(bins, tuple(a3), 1)
    # Filtering is left as an exercise
    return bins.ravel()

def f_py(text):
    counts = [0] * 1000
    for idx in range(len(text)-2):
        counts[int(text[idx:idx+3])] += 1
    return counts

import numpy as np
import types
from timeit import timeit
for n in (10, 1000, 1000000):
    data = setup_data(n)
    ref = f_np(**data)
    print(f'n = {n}')
    for name, func in list(globals().items()):
        if not name.startswith('f_') or not isinstance(func, types.FunctionType):
            continue
        try:
            assert np.all(ref == func(**data))
            print("{:16s}{:16.8f} ms".format(name[2:], timeit(
                'f(**data)', globals={'f':func, 'data':data}, number=10)*100))
        except:
            print("{:16s} apparently crashed".format(name[2:]))

# n = 10
# np                    0.03481400 ms
# py                    0.00669330 ms
# n = 1000
# np                    0.11215360 ms
# py                    0.34836530 ms
# n = 1000000
# np                   82.46765980 ms
# py                  360.51235450 ms

def find_numbers(str_num):
    final_dict = {}
    buffer = {}
    for idx in range(len(str_num) - 3):
        num = int(str_num[idx:idx + 3])
        if num not in buffer:
            buffer[num] = 0
        buffer[num] += 1
        if buffer[num] > 1:
            final_dict[num] = buffer[num]
    return final_dict

>>> find_numbers("123412345123456")
{345: 2, 234: 3, 123: 3}

def calc_repeating_digits(number):

    hash = {}

    for i in range(len(str(number))-2):

        current_three_digits = number[i:i+3]
        if current_three_digits in hash.keys():
            hash[current_three_digits] += 1

        else:
            hash[current_three_digits] = 1

    return hash