정렬 순서 인덱스

Question

에 의해 목록은 우리가 나는 다음과 같은 두 시퀀스가 ​​있다고 가정하자

val index = Seq(2,5,1,4,7,6,3) 
val unsorted = Seq(7,6,5,4,3,2,1) 

첫 번째는 두 번째 정렬해야하는 인덱스입니다. 내 현재 솔루션은 인덱스를 탐색하고 정렬되지 않은 시퀀스에서 발견 된 요소를 사용하여 새 시퀀스를 구성하는 것입니다.

val sorted = index.foldLeft(Seq[Int]()) { (s, num) => 
    s ++ Seq(unsorted.find(_ == num).get) 
} 

그러나이 솔루션은 매우 비효율적이며 오류가 발생하는 것으로 보입니다. 매 반복마다 정렬되지 않은 전체 시퀀스를 검색합니다. 그리고 인덱스와 정렬되지 않은 목록이 동기화되어 있지 않으면 오류가 발생하거나 요소가 생략됩니다. 두 경우 모두 not in sync 요소는 정렬 된 순서에 추가되어야합니다.

이 문제에 대한보다 효과적이고 확실한 해결책이 있습니까? 아니면이 패러다임에 맞는 정렬 알고리즘이 있습니까?

---

주 :이 구성 예이다. 실제로 mongodb 문서의 목록을 문서 ID의 정렬 된 목록으로 정렬하고 싶습니다. 내 문제에 대한 더 빠르고 스칼라 틱 솔루션을 보이기 때문에

---

업데이트 1

나는 마리우스 다닐라에서 답을 선택했습니다. 그것은 동기화 항목 솔루션과 함께 제공되지 않습니다,하지만 쉽게 구현할 수 있습니다.

그래서 여기에 업데이트 된 솔루션입니다 :

def sort[T: ClassTag, Key](index: Seq[Key], unsorted: Seq[T], key: T => Key): Seq[T] = { 
    val positionMapping = HashMap(index.zipWithIndex: _*) 
    val inSync = new Array[T](unsorted.size) 
    val notInSync = new ArrayBuffer[T]() 
    for (item <- unsorted) { 
    if (positionMapping.contains(key(item))) { 
     inSync(positionMapping(key(item))) = item 
    } else { 
     notInSync.append(item) 
    } 
    } 

    inSync.filterNot(_ == null) ++ notInSync 
} 

---

업데이트 2

Bask.cc에 의해 제안 접근 정답을 보인다. 또한 동기화되지 않은 문제는 고려하지 않지만 쉽게 구현할 수도 있습니다.

val index: Seq[String] 
val entities: Seq[Foo] 
val idToEntityMap = entities.map(e => e.id -> e).toMap 
val sorted = index.map(idToEntityMap) 
val result = sorted ++ entities.filterNot(sorted.toSet) 

Answer 1

은 왜 모음을 정렬 할 않는다 , 당신은 이미 인덱스 컬렉션을 정렬했을 때? 그냥지도를 사용할 수 있습니다

> 사실 mongodb 문서의 목록을 문서 ID의 정렬 된 목록으로 정렬하고 싶습니다.

val ids: Seq[String] 
val entities: Seq[Foo] 
val idToEntityMap = entities.map(e => e.id -> e).toMap 

ids.map(idToEntityMap _) 

Answer 2

나는 당신이 사용하는 언어를 모릅니다. 그러나 언어에 관계없이 이것이 문제를 해결했을 것입니다.

첫 번째 목록 (여기 'index')에서 키를 문서 ID로 사용하고 값을 정렬 된 순서로 문서의 위치로 사용하는 해시 테이블을 만듭니다.

이제 문서 목록을 탐색 할 때 문서 ID를 사용하여 해시 테이블을 조회 한 다음 정렬 된 순서로 위치를 가져올 수 있습니다. 그럼 내가 미리 할당 된 메모리에서 정렬이 얻은 순서를 사용합니다.

참고 : 문서 수가 적은 경우 해시 테이블 대신 사전 할당 된 테이블을 사용하고 문서 ID를 사용하여 직접 색인을 생성 할 수 있습니다.

Answer 3

평면 매핑 정렬되지 않은 목록을 통해 인덱스 (인덱스가 find가 None 반환하기 때문에 그냥 떨어있어 발견되지 않는 경우) 안전한 버전이 될 것으로 보인다 : 그것은 여전히 ​​정렬되지 않은를 통과 할 수있다

index.flatMap(i => unsorted.find(_ == i)) 

을 매회 목록을 표시합니다 (최악의 경우 O (n^2)). 당신이보기에 나는 더 효율적인 해결책이 있다는 것을 확신하지 못합니다.

Answer 4

내가 할 수있는 최선의 방법은 정렬되지 않은 데이터에서 Map을 만들고 맵 조회 (기본적으로 이전 포스터에서 제안한 해시 테이블)를 사용하는 것입니다. 코드는 외모와 같은 :

val unsortedAsMap = unsorted.map(x => x -> x).toMap 
index.map(unsortedAsMap) 

또는 해시 미스의 가능성이 있다면 :

val unsortedAsMap = unsorted.map(x => x -> x).toMap 
index.flatMap(unsortedAsMap.get) 

그것은 시간 *에 O(n)하지만이 O(n) 공간을 사용 당신이 공간 시간을 교환하고 있습니다.

누락 된 값을 처리하는 약간 더 정교한 버전에 대한

, 시도 :

import scala.collection.JavaConversions._ 
import scala.collection.mutable.ListBuffer 

val unsortedAsMap = new java.util.LinkedHashMap[Int, Int] 
for (i <- unsorted) unsortedAsMap.add(i, i) 

val newBuffer = ListBuffer.empty[Int] 
for (i <- index) { 
    val r = unsortedAsMap.remove(i) 
    if (r != null) newBuffer += i 
    // Not sure what to do for "else" 
} 

for ((k, v) <- unsortedAsMap) newBuffer += v 

newBuffer.result() 

을 그 첫 번째 장소에서 MongoDB를 데이터베이스가 있다면, 당신은 더 나은 인덱스 데이터베이스에서 직접 문서를 검색 할 수 있습니다, 그래서 뭔가를 같은 :

index.map(lookupInDB) 

을 * 스칼라의 표준 불변의지도 O(log n)이기 때문에 기술적으로는 O(n log n),하지만 당신은 항상 O(1)

입니다 변경 가능한 맵을 사용할 수 있습니다 당신이 지퍼 정렬 압축 해제를 사용할 수 있습니다이 경우

Answer 5

:

(unsorted zip index).sortWith(_._2 < _._2).unzip._1

, BTW 당신이 더 나은 솔루션 $orderBy를 사용하여 DB 측에서 목록을 정렬하는 것입니다 수 있다면.

Answer 6

확인.

처음부터 시작해 보겠습니다. unsorted 목록을 다시 검색한다는 사실 외에도 Seq 개체는 기본적으로 List 컬렉션을 생성합니다. 따라서 foldLeft에서 매번 목록의 끝에 요소를 추가하고 있는데 이것은 O(N^2) 작업입니다.

개선점은

val sorted_rev = index.foldLeft(Seq[Int]()) { (s, num) => 
    unsorted.find(_ == num).get +: s 
} 
val sorted = sorted_rev.reverse 

것하지만 여전히 O(N^2) 알고리즘이다. 우리는 더 잘할 수 있습니다.

다음 정렬 기능이 작동해야합니다

def sort[T: ClassTag, Key](index: Seq[Key], unsorted: Seq[T], key: T => Key): Seq[T] = { 
    val positionMapping = HashMap(index.zipWithIndex: _*) //1 
    val arr = new Array[T](unsorted.size) //2 
    for (item <- unsorted) { //3 
    val position = positionMapping(key(item)) 
    arr(position) = item 
    } 
    arr //6 
} 

기능은 key 기능을 사용하면하려는 목적에서 ID를 추출하는 데 사용되는 인덱스 index의 순서로 항목 unsorted의 목록을 정렬 정렬하려면.

1 행은 역 색인을 생성하여 각 객체 ID를 최종 위치에 매핑합니다.

줄 2는 정렬 된 시퀀스를 보유 할 배열을 할당합니다. 우리는 일정 시간 임의의 위치 설정 성능이 필요하기 때문에 배열을 사용하고 있습니다.

정렬되지 않은 항목의 순서를 통과하고 각 항목을 배치 할 3 행에서 시작하는 루프는 배열이 WrappedArray 래퍼를 사용하여 Seq로 암시 적으로 변환 돌아갑니다 positionMapping 역 인덱스

6 호선을 이용하여 위치를 의미하는 것 .

반전 색인은 변경 불가능한 HashMap이므로 일반적인 경우에는 조회가 일정 시간이 걸립니다. 실제 역 색인 생성은 O(N_Index) 시간이 걸립니다. 여기서 N_Index은 색인 시퀀스의 크기입니다. 정렬되지 않은 시퀀스를 순회하는 경우 O(N_Unsorted) 시간이 걸립니다. 여기서 N_Unsorted은 정렬되지 않은 시퀀스의 크기입니다.

복잡성은 O(max(N_Index, N_Unsorted))입니다. 상황에 따라 최선을 다할 것으로 생각됩니다.

특정 예를 들어

, 당신과 같이 함수를 호출 할 것이다 :

val sorted = sort(index, unsorted, identity[Int]) 

을 실제 사례를 들어, 아마 이렇게 될 것이다 :

val sorted = sort(idList, unsorted, obj => obj.id) 

Answer 7

이 정확하게 사용 사례에 매핑 할 수 있지만 명의 Google 찾을 수도 있습니다 유용 : 또한

scala> val ids = List(3, 1, 0, 2) 
ids: List[Int] = List(3, 1, 0, 2) 

scala> val unsorted = List("third", "second", "fourth", "first") 
unsorted: List[String] = List(third, second, fourth, first) 

scala> val sorted = ids map unsorted 
sorted: List[String] = List(first, second, third, fourth)