백만 개의 숫자 문자열이 주어지면 반복되는 모든 3자리 숫자를 반환합니다.
몇 달 전 뉴욕의 헤지펀드 회사와 인터뷰를 했는데 아쉽게도 데이터/소프트웨어 엔지니어로서 인턴십 제안을 받지 못했습니다. (그들은 솔루션이 파이썬에 있는지도 요청했습니다.)
첫 번째 면접 문제를 거의 망쳤어요
질문: 백만 개의 숫자(예: Pi)가 주어지면, 반복되는 모든 3자리 숫자와 1보다 큰 반복 횟수를 반환하는 함수/프로그램을 작성합니다.
를 들어,과 같다면: " " " " " " " " " "123412345123456그러면 함수/프로그램이 반환됩니다.
123 - 3 times
234 - 3 times
345 - 2 times
그들은 제가 인터뷰에 실패한 후에 해결책을 제시하지 않았지만, 가능한 모든 결과가 다음 사이에 있기 때문에 해결책에 대한 시간 복잡도가 1,000으로 일정하다고 말했습니다.
000 --> 999
지금 생각해보니, 일정한 시간 알고리즘을 생각해 내는 것은 불가능할 것 같습니다.그런가요?
당신은 가볍게 시작했고, 아마도 당신은 퀀트들이 기본 알고리즘을 이해하지 못하는 헤지 펀드에서 일하고 싶지 않을 것입니다 :-)
에서 임의 크기의 데이터 구조를 처리할 수 있는 방법은 없습니다.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)]
물론 출력 형식을 원하는 대로 수정할 수도 있습니다.
그리고, 마지막으로, 그들에게 거의 확실히 문제가 없다고 말함으로써.O(n)위의 코드가 1백만 자리 문자열에 대한 결과를 0.5초 미만으로 전달하기 때문에 해결책입니다., 가 걸리기 되는 것 . 10,000,000자의 문자열은 3.5초 100,000,000자의 문자열은 36초입니다.
그리고, 만약 그들이 그것보다 더 나은 것을 필요로 한다면, 이런 종류의 것들을 병렬화시킬 수 있는 방법들이 있습니다. 속도를 크게 높일 수 있습니다.
물론 GIL 때문에 단일 파이썬 인터프리터 내에서는 아니지만 문자열을 다음과 같은 것으로 분할할 수 있습니다(오버랩:vv경계 영역의 적절한 처리를 위해 필요함):
vv
123412 vv
123451
5123456
당신은 이것들을 별도의 작업자들에게 나누어 주고 그 결과를 나중에 조합할 수 있습니다.
입력을 분할하고 출력을 결합하면 작은 문자열(그리고 심지어는 백만 자리 문자열)을 사용하여 절약할 수 없게 될 가능성이 높지만, 훨씬 더 큰 데이터 세트의 경우에는 차이가 있을 수 있습니다.물론 제가 늘 하는 "측정, 추측하지 마세요"라는 구호가 여기에 적용됩니다.
이 만트라는 Python을 완전히 우회하고 더 빠를 수 있는 다른 언어를 사용하는 것과 같은 다른 가능성에도 적용됩니다.
예를 들어, 이전 Python 코드와 동일한 하드웨어에서 실행되는 다음 C 코드는 1억 자리를 0.6초 만에 처리하며, 이는 Python 코드가 1백만을 처리한 것과 거의 같은 시간입니다.다시 말해, 훨씬 더 빠릅니다.
#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;
}
일정한 시간은 불가능합니다.100만 자리는 모두 한 번 이상 살펴야 하므로 O(n)의 시간 복잡도이며, 여기서 n = 100만입니다.
간단한 O(n) 솔루션의 경우 가능한 각 3자리 숫자의 발생 횟수를 나타내는 크기 1000의 배열을 만듭니다.한 번에 1자리씩 전진하고, 첫 번째 인덱스 == 0, 마지막 인덱스 == 999997, 증분 배열 [3자리 숫자]를 사용하여 히스토그램을 만듭니다(가능한 각 3자리 숫자에 대한 발생 횟수).그런 다음 카운트가 1보다 큰 배열의 내용을 출력합니다.
제가 아래에 제시한 답변에 비해 100만은 작습니다.인터뷰에서 솔루션을 잠시도 쉬지 않고 실행할 수 있어야 하기 때문에 다음은 2초 이내에 작동하며 필요한 결과를 제공합니다.
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)
면접관이 표준 도서관 컬렉션의 사용법을 찾고 있기를 바랍니다.카운터 클래스.
병렬 실행 버전
저는 더 많은 설명과 함께 이것에 대한 블로그 게시물을 작성했습니다.
간단한 O(n) 솔루션은 각 3자리 숫자를 세는 것입니다.
for nr in range(1000):
cnt = text.count('%03d' % nr)
if cnt > 1:
print '%03d is found %d times' % (nr, cnt)
이렇게 하면 100만 자리를 모두 1000번 검색할 수 있습니다.
숫자를 한 번만 통과:
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)
한 하는 것보다 두 배 더 빠르다는 것을 보여줍니다.count.
이것은 "합의" O(n) 알고리즘의 NumPy 구현입니다. 가는 동안 모든 세쌍둥이와 빈을 거닐어보세요.빈은 "385"라고 말하면 O(1) 작업인 bin[3, 8, 5]에 하나를 추가하여 수행됩니다.은 은다음과같배니다됩열이빈▁a▁in로 정리되어 .10x10x10큐브입니다. 바인딩이 완전히 벡터화되었기 때문에 코드에 루프가 없습니다.
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:]))
당연히 NumPy는 대형 데이터 세트에서 @Daniel의 순수 Python 솔루션보다 약간 빠릅니다.샘플 출력:
# 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}
이 솔루션은 제공된 문자열의 길이인 n에 대해 O(n)로 실행되며, 제 생각에 이것이 당신이 얻을 수 있는 최선입니다.
제가 알기로는 당신은 일정한 시간 내에 해결책을 가질 수 없습니다.백만 자리 숫자보다 하나 이상의 패스가 필요합니다(문자열로 가정).백만 길이의 숫자에 대해 3자리 롤링 반복을 수행하고 해시 키가 이미 있으면 값을 1로 늘리거나 사전에 없는 경우 새 해시 키(값 1로 초기화됨)를 생성할 수 있습니다.
코드는 다음과 같습니다.
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
항목 값이 1보다 큰 키까지 필터링할 수 있습니다.
다른 답변에서 언급한 것처럼 n자리 이상을 찾아야 하기 때문에 일정한 시간 내에 이 알고리즘을 수행할 수 없습니다.선형 시간이 가장 빠릅니다.
그러나 알고리즘은 O(1) 공간에서 수행할 수 있습니다.각 3자리 숫자의 카운트만 저장하면 되므로 1,000개의 항목 배열이 필요합니다.그런 다음 번호를 스트리밍할 수 있습니다.
제 생각에는 면접관이 해결책을 제시할 때 말을 잘못했거나 "일정한 공간"이라고 말할 때 "일정한 시간"이라고 잘못 들은 것 같습니다.
제 대답은 이렇습니다.
from timeit import timeit
from collections import Counter
import types
import random
def setup_data(n):
digits = "0123456789"
return dict(text = ''.join(random.choice(digits) for i in range(n)))
def f_counter(text):
c = Counter()
for i in range(len(text)-2):
ss = text[i:i+3]
c.update([ss])
return (i for i in c.items() if i[1] > 1)
def f_dict(text):
d = {}
for i in range(len(text)-2):
ss = text[i:i+3]
if ss not in d:
d[ss] = 0
d[ss] += 1
return ((i, d[i]) for i in d if d[i] > 1)
def f_array(text):
a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)]
for n in range(len(text)-2):
i, j, k = (int(ss) for ss in text[n:n+3])
a[i][j][k] += 1
for i, b in enumerate(a):
for j, c in enumerate(b):
for k, d in enumerate(c):
if d > 1: yield (f'{i}{j}{k}', d)
for n in (1E1, 1E3, 1E6):
n = int(n)
data = setup_data(n)
print(f'n = {n}')
results = {}
for name, func in list(globals().items()):
if not name.startswith('f_') or not isinstance(func, types.FunctionType):
continue
print("{:16s}{:16.8f} ms".format(name[2:], timeit(
'results[name] = f(**data)', globals={'f':func, 'data':data, 'results':results, 'name':name}, number=10)*100))
for r in results:
print('{:10}: {}'.format(r, sorted(list(results[r]))[:5]))
배열 조회 방법은 매우 빠릅니다(@paul-panzer의 numpy 방법보다 더 빠름!).물론, 그것은 완성된 후에 기술적으로 완성되지 않았기 때문에, 그것은 발전기를 돌려주는 것이기 때문에 부정행위를 합니다.또한 값이 이미 존재하는 경우 모든 반복을 확인할 필요가 없으므로 많은 도움이 될 수 있습니다.
n = 10
counter 0.10595780 ms
dict 0.01070654 ms
array 0.00135370 ms
f_counter : []
f_dict : []
f_array : []
n = 1000
counter 2.89462101 ms
dict 0.40434612 ms
array 0.00073838 ms
f_counter : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_dict : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_array : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
n = 1000000
counter 2849.00500992 ms
dict 438.44007806 ms
array 0.00135370 ms
f_counter : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_dict : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_array : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
이미지 응답:
미닫이창 같아요.
제 솔루션은 다음과 같습니다.
from collections import defaultdict
string = "103264685134845354863"
d = defaultdict(int)
for elt in range(len(string)-2):
d[string[elt:elt+3]] += 1
d = {key: d[key] for key in d.keys() if d[key] > 1}
루프에 대한 창의성이 약간 있는 경우(예: True/False/None이 포함된 추가 조회 목록) 마지막 줄을 제거할 수 있습니다. 마지막 줄은 해당 지점까지 방문한 적이 있는 키만 만들 수 있습니다.도움이 되길 바랍니다 :)
-C.의 관점에서 -int 3-d 배열 결과[10][10]; -0번째 위치에서 n번째 위치로 이동합니다. 여기서 n은 문자열 배열의 크기입니다. -각 위치에서 현재, 다음, 다음을 확인합니다. -cntras 결과[current][next][next]+; -cntras 결과값을 인쇄합니다.
results[1][2][3]
results[2][3][4]
results[3][4][5]
results[4][5][6]
results[5][6][7]
results[6][7][8]
results[7][8][9]
-O(n) 시간입니다. 비교가 필요 없습니다. -여기서는 배열을 분할하고 파티션 주위의 일치 항목을 계산하여 몇 가지 병렬 작업을 실행할 수 있습니다.
inputStr = '123456123138276237284287434628736482376487234682734682736487263482736487236482634'
count = {}
for i in range(len(inputStr) - 2):
subNum = int(inputStr[i:i+3])
if subNum not in count:
count[subNum] = 1
else:
count[subNum] += 1
print count
언급URL : https://stackoverflow.com/questions/47581326/given-a-string-of-a-million-numbers-return-all-repeating-3-digit-numbers
'sourcecode' 카테고리의 다른 글
| MariaDB 기반 모델링 도구 (0) | 2023.09.05 |
|---|---|
| LESS 변수의 알파 불투명도 수정 (0) | 2023.09.05 |
| jQuery로 바인딩된 이벤트 순서 지정 방법 (0) | 2023.09.05 |
| php(?int)에서 형식 선언 전 물음표(?)는 무엇을 의미합니까? (0) | 2023.09.05 |
| Spring MVC: 여러 URL을 동일한 컨트롤러에 매핑 (0) | 2023.09.05 |