문자열 멤버의 조건과 일치하는 컬렉션에서 개체를 찾는 가장 빠른 방법

StackOverflow https://stackoverflow.com/questions/97329

문제

컬렉션(배열, 일반 목록 등)이 있다고 가정해 보겠습니다. 가장 빠른 이 문제에 대한 해결책) 특정 클래스의 이름을 지정해 보겠습니다. ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
}

컬렉션에 50,000개의 항목이 모두 메모리에 있다고 가정합니다.이제 다음과 같이 bar 멤버의 조건을 따르는 컬렉션의 모든 인스턴스를 최대한 빨리 얻고 싶습니다.

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

최대한 빨리 결과를 얻으려면 어떻게 해야 합니까?일부 고급 색인 기술과 데이터 구조를 고려해야 합니까?

이 문제에 대한 애플리케이션 도메인은 쿼리를 가져오고 결과적으로 제안 모음을 제공하는 자동 완성기입니다.조건이 이보다 더 복잡해지지 않는다고 가정합니다.또한 많은 검색이 있을 것이라고 가정합니다.

도움이 되었습니까?

해결책

조건 절이 "무엇이든"이 될 수 있다는 제약 조건을 사용하면 전체 목록을 검색하고 조건을 적용하는 것으로 제한됩니다.

조건 절에 제한이 있는 경우 데이터를 구성하여 쿼리를 보다 효율적으로 처리할 수 있습니다.

예를 들어, "byFirstLetter" 사전이 포함된 코드 샘플은 "endsWith" 쿼리에 전혀 도움이 되지 않습니다.

따라서 실제로 해당 데이터에 대해 수행하려는 쿼리가 중요합니다.

데이터베이스에서 이 문제는 "쿼리 최적화 프로그램"의 부담입니다.일반적인 데이터베이스에서 인덱스가 없는 데이터베이스가 있는 경우 분명히 모든 쿼리는 테이블 스캔이 됩니다.테이블에 인덱스를 추가하면 최적화 프로그램은 해당 데이터를 사용하여 데이터에 더 잘 접근할 수 있는 보다 정교한 쿼리 계획을 세울 수 있습니다.이것이 본질적으로 당신이 설명하는 문제입니다.

쿼리 유형의 보다 구체적인 하위 집합이 있으면 어떤 구조가 가장 적합한지에 대해 더 나은 결정을 내릴 수 있습니다.또한, 데이터의 양을 고려해야 합니다.각각 100바이트 미만의 10개 요소 목록이 있는 경우 데이터 양이 매우 작기 때문에 모든 항목을 검색하는 것이 가장 빠른 작업일 수 있습니다.분명히 100만 요소로 확장되지는 않지만 영리한 액세스 기술이라 할지라도 설정, 유지 관리(인덱스 유지 관리와 같은) 및 메모리 비용이 발생합니다.

편집하다, 댓글을 기반으로

자동 완성기인 경우 데이터가 정적이면 정렬하고 이진 검색을 사용합니다.당신은 정말로 그보다 더 빨리 얻을 수 없을 것입니다.

데이터가 동적이면 균형 트리에 저장하고 검색하세요.이는 사실상 이진 검색이므로 데이터를 무작위로 계속 추가할 수 있습니다.

다른 것은 이러한 개념에 대한 전문화입니다.

다른 팁

var Answers = myList.Where(item => item.bar.StartsWith(query) || item.bar.EndsWith(query));

제 생각에는 그게 가장 쉽고 빠르게 실행되어야 한다고 생각합니다.

이해가 잘 안가는데...실제로 할 수 있는 일은 규칙을 최적화하는 것뿐입니다. 이는 가장 빨라야 하는 부분입니다.더 많은 하드웨어를 투입하지 않고는 루프 속도를 높일 수 없습니다.

코어나 머신이 여러 개인 경우 병렬화할 수 있습니다.

나는 지금 Java를 사용하고 있지 않지만 다음 사항에 대해 생각해 볼 것입니다.

목록을 어떻게 작성하고 있나요?아마도 비교 시간을 줄이는 방식으로 이미 주문한 것을 만들 수 있을 것입니다.

컬렉션을 통해 직선 루프를 수행하는 경우 컬렉션을 배열로 저장하거나 연결 목록으로 저장하는 것 사이에 큰 차이가 없습니다.

결과를 저장하는 경우 결과를 수집하는 방법에 따라 구조가 달라질 수 있습니다(그러나 Java의 일반 구조가 스마트하다고 가정하면 그렇지 않습니다).내가 말했듯이 나는 Java를 사용하지 않지만 일반 연결 목록이 꼬리 포인터를 유지할 것이라고 가정합니다.이 경우에는 실제로 차이가 발생하지 않습니다.기본 배열과 연결 목록 구현에 대해 더 잘 알고 바이트 코드에서 어떻게 보이는지에 대해 더 잘 아는 사람은 꼬리 포인터를 사용하여 연결 목록에 추가하는 것이 더 빠른지 또는 배열에 삽입하는 것이 더 빠른지 알려줄 수 있습니다. ).반면에 배열을 사용하려면 결과 집합의 크기를 알아야 하거나 일부 저장 공간을 희생하고 반복하는 전체 컬렉션만큼 크게 만들어야 합니다.

어떤 비교가 사실일 가능성이 가장 높은지 파악하여 비교 쿼리를 최적화하고 이를 먼저 수행하는 것도 도움이 될 수 있습니다.즉:일반적으로 컬렉션 구성원이 쿼리로 시작하는 시간의 10%이고 쿼리로 끝나는 시간의 30%인 경우 종료 비교를 먼저 수행하는 것이 좋습니다.

특정 예의 경우 쿼리로 시작하는 첫 번째 항목을 바이너리로 자르고 그렇지 않은 다음 항목에 도달하면 일찍 종료할 수 있으므로 컬렉션을 정렬하는 것이 도움이 됩니다.두 번째 절에 대한 각 문자열의 역순으로 정렬된 컬렉션 항목에 대한 포인터 테이블을 생성할 수도 있습니다.

일반적으로 쿼리의 구조를 미리 알고 있으면 컬렉션을 적절하게 정렬할 수 있습니다(또는 절이 여러 개인 경우 컬렉션에 대해 정렬된 인덱스를 여러 개 구축).그렇지 않으면 선형 검색보다 더 나은 결과를 얻을 수 없습니다.

목록을 한 번 채운 다음 많은 조회(수천 개 이상)를 수행하는 경우 값으로 시작/끝나는 값을 실제 값에 매핑하는 일종의 조회 사전을 만들 수 있습니다.이는 빠른 조회이지만 훨씬 더 많은 메모리를 사용하게 됩니다.그렇게 많은 조회를 수행하지 않거나 목록을 적어도 반쯤 자주 다시 채울 것이라는 것을 알고 있다면 CQ가 제안한 LINQ 쿼리를 사용하겠습니다.

일종의 인덱스를 생성하면 속도가 더 빨라질 수 있습니다.

우리는 다음과 같은 인덱스를 만들 수 있습니다:

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

그런 다음 다음과 같이 사용하십시오.

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

이제 예제에서처럼 많은 ClassFoo를 반복할 필요는 없지만 다시 인덱스를 최신 상태로 유지해야 합니다.더 빠르다는 보장은 없지만 확실히 더 복잡합니다.

상황에 따라 다릅니다.모든 객체가 항상 메모리에 로드됩니까?로드할 수 있는 개체의 수가 제한되어 있습니까?쿼리에서 아직 로드되지 않은 개체를 고려해야 합니까?

컬렉션이 커지면 반드시 인덱스를 사용하겠습니다.

실제로 컬렉션이 임의의 크기로 커질 수 있고 컬렉션을 메모리에 모두 담을 수 있을지 확신할 수 없다면 ORM, 메모리 내 데이터베이스 또는 다른 내장 데이터베이스를 살펴보겠습니다.ORM용 DevExpress 또는 인메모리 데이터베이스용 SQLite.Net의 XPO가 떠오릅니다.

여기까지 진행하고 싶지 않다면 클래스 참조에 매핑되는 "bar" 멤버 참조로 구성된 간단한 인덱스를 만드세요.

가능한 기준 집합이 고정되어 있고 작은 경우 목록의 각 요소에 비트마스크를 할당할 수 있습니다.비트마스크의 크기는 기준 집합의 크기입니다.요소를 생성하거나 목록에 추가할 때 어떤 기준을 충족하는지 확인한 다음 이 요소의 비트마스크에 해당 비트를 설정합니다.목록의 요소를 일치시키는 것은 해당 비트마스크를 대상 비트마스크와 일치시키는 것만큼 쉽습니다.보다 일반적인 방법은 Bloom 필터입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top