짧은 링크 충돌을 처리하기위한 가장 빠른 C# 구현

Question

링크를 단축하고있는 서비스에 대한 짧은 코드를 미리 생성하고 있습니다. 그것은 일반적인 링크 단축키가 아니므로 선반을 벗어날 수는 없습니다. 초당 약 1000 개의 단축 줄을 처리해야하기 때문입니다.

링크를 빠르게 생성하기 위해 조회 테이블에 200,000 개의 짧은 링크를 추가하기 위해 12 시간마다 실행되는 서비스가 있습니다.

짧은 링크 테이블이 길어지면 요청하는 짧은 링크에 대한 요구 사항을 따라 잡을 수 없을 정도로 서비스가 더 오래 걸립니다.

단축 링크는 1.8M 행입니다. 우리는 우리가 다 떨어지기 전에 남은 280k 링크가 있습니다. 그리고 지금 200k 링크를 생성하는 데 1 시간 이상 걸립니다.

저는 분명히 뭔가 잘못하고 있습니다. 아마도 나는 비교하기 위해 List<string>만을 사용하고있을 것입니다.

Stopwatch sw = Stopwatch.StartNew(); 
LtsDataContext ldc = new LtsDataContext(); 
List<string> currentCodes = ldc.ShortUrls.Select(s => s.ShortCode).ToList(); 
currentCodes = 
    currentCodes.Union(ldc.FastShortCodes.Select(s => s.ShortCode)).ToList(); 

int count = args.Length > 0 ? int.Parse(args[0]) : 200000; 

List<string> newCodes = new List<string>(count); 

for (int i = 0; i < count; i++) 
{ 
    string newCode = Guid.NewGuid().ToString("N").Substring(0, 8); 
    while (currentCodes.Contains(newCode) || newCodes.Contains(newCode)) 
     newCode = Guid.NewGuid().ToString("N").Substring(0, 8); 
    newCodes.Add(newCode); 
} 

ldc.FastShortCodes.InsertAllOnSubmit(newCodes.Select(s => 
    new FastShortCode() { ShortCode = s })); 
ldc.SubmitChanges(); 
Console.Write((decimal)sw.ElapsedMilliseconds/(decimal)1000); 
Console.ReadKey(); 

Answer 1

GUID 조각을 사용하면 크고 큰 테이블과의 충돌을 확인해야합니다.

순차 키를 만들려하지 않는다고 가정합니다. URL 순응에 취약하기 때문에 순차 키를 만들고 싶지는 않지만 순차적으로 시작한 다음 순종해야합니다. 주석 기의 제안에가는

편집

, I 것 : 당신은 어떤 충돌이없는 것, 랜덤 비트는 사람이 무작위로 하나의 밖으로 명중 얻을 것이다 URL을 시도하는 것을 의미합니다

1. take a sequential key 
2. shift left 8 
3. add a random value between 0 and 255 
4. encode base-62 (0-9,A-Z,a-z) 

매 255 회 시도 중.

currentCodes.Contains(newCode) || newCodes.Contains(newCode) 

이이 문제를 설명하는 각 추가로 더 걸릴 것 :

Answer 2

가 왜 currentCodes 및 newCodes에 대한 Dictionary를 사용하지 않는 : 다음 코드 블록은? List의 Contains 메서드는 O (1)에서 실행되는 Dictionary과 달리 모든 목록 항목 O (n)을 트래버스해야합니다.

EDIT1 어쨌든 데이터베이스에 모든 링크를 저장하는 경우 왜 GUID가 필요합니까? 링크에서 데이터베이스의 기본 키를 사용하지 않는 이유는 무엇입니까? 코드가 이미 존재하는 동반 할 가능성 이후

EDIT2 는 다시 (낙관적 삽입을)를 시도하십시오 삽입을 시도하고 예외를 잡을 수있는 매우 낮다.

Answer 3

다음은이 라인에 문제가 있습니다. 이 수학적 복잡성에 관심이 있다면 의심 스럽지만 (N * N)/2에 가까울 것입니다.

해결책은 HashTable입니다.

Answer 4

내가 틀렸다면 정정하십시오. 그러나 짧은 링크 (180 만 개) 전체 목록을 목록에로드 한 다음 Contains 함수로 검색하는 것처럼 보입니다. @Jeff Foster가 지적한대로 O (n) 연산.

더 낙관적 인 방법을 사용하지 않는 이유는 무엇입니까? 데이터베이스에서 ShortUrls/FastShortCodes 테이블의 ShortCode 열에 고유 제한 조건을 추가하십시오. 그런 다음 새로운 짧은 코드를 생성하고 삽입하십시오. 고유 한 제약 조건 (너무 자주 발생하지 않아야 함)에 실패하면 예외를 catch하고 다시 시도하십시오.

나는 또한 GUID의 부분 문자열을 사용하여 자신을 15 자 (0-9, A-F)로 제한한다는 것을 동의합니다. 나는 적어도 영숫자 (0-9, A-Z)를 사용하는 방법을 찾고 있는데, 이는 충돌하는 횟수를 현저히 줄여 줄 것입니다.