Sắp xếp một danh sách bằng một chỉ số lệnh

Question

Chúng ta hãy giả định rằng tôi có hai chuỗi sau:

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

Đầu tiên là chỉ số mà thứ hai nên được sắp xếp. Giải pháp hiện tại của tôi là duyệt qua chỉ mục và xây dựng một chuỗi mới với các phần tử tìm thấy từ chuỗi chưa phân loại.

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

Nhưng giải pháp này có vẻ rất không hiệu quả và dễ bị lỗi. Trên mỗi lần lặp lại, nó tìm kiếm toàn bộ chuỗi chưa phân loại. Và nếu chỉ mục và danh sách chưa được phân loại không đồng bộ, thì một lỗi sẽ bị ném hoặc một phần tử sẽ bị bỏ qua. Trong cả hai trường hợp, các phần tử không đồng bộ nên được nối vào trình tự được sắp xếp.

Có giải pháp hiệu quả và vững chắc hơn cho vấn đề này không? Hoặc là có một thuật toán sắp xếp phù hợp với mô hình này?

---

Lưu ý: Đây là ví dụ được tạo. Trong thực tế, tôi muốn sắp xếp một danh sách các tài liệu mongodb bởi một danh sách thứ tự của tài liệu Id.

---

Cập nhật 1

Tôi đã chọn câu trả lời từ Marius Danila vì nó có vẻ là giải pháp nhanh nhất và scala-ish hơn cho vấn đề của tôi. Nó không đi kèm với một giải pháp không đồng bộ trong mục, nhưng điều này có thể dễ dàng thực hiện.

Vì vậy, đây là giải pháp Cập nhật:

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 
} 

---

Cập nhật 2

Phương pháp được đề xuất bởi Bask.cc dường như câu trả lời đúng. Nó cũng không xem xét vấn đề không đồng bộ, nhưng điều này cũng có thể được thực hiện dễ dàng.

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

Tại sao bạn muốn sắp xếp bộ sưu tập , khi bạn đã có bộ sưu tập chỉ mục được sắp xếp? Bạn chỉ có thể sử dụng bản đồ

Liên quan> Trong thực tế, tôi muốn sắp xếp danh sách tài liệu mongodb theo danh sách thứ tự của ID tài liệu.

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

ids.map(idToEntityMap _) 

Answer 2

Tôi không biết ngôn ngữ bạn đang sử dụng. Nhưng không phân biệt ngôn ngữ này là cách tôi sẽ giải quyết vấn đề.

Từ danh sách đầu tiên (tại đây 'chỉ mục') tạo bảng băm lấy khóa làm id tài liệu và giá trị làm vị trí của tài liệu theo thứ tự được sắp xếp.

Bây giờ khi duyệt qua danh sách tài liệu, tôi sẽ tra cứu bảng băm bằng cách sử dụng id tài liệu và sau đó nhận vị trí cần theo thứ tự được sắp xếp. Sau đó, tôi sẽ sử dụng thứ tự thu được này để sắp xếp trong một bộ nhớ được phân bổ trước.

Lưu ý: nếu số lượng tài liệu nhỏ thì thay vì sử dụng hashtable u có thể sử dụng bảng được phân bổ trước và lập chỉ mục trực tiếp bằng id tài liệu.

Answer 3

Flat Mapping chỉ số trong danh sách được phân loại có vẻ là một phiên bản an toàn hơn (nếu chỉ số không tìm thấy nó chỉ giảm từ find trả về một None):

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

Nó vẫn phải đi qua không được phân loại liệt kê mọi lúc (trường hợp xấu nhất là O (n^2)). Với ví dụ của bạn tôi không chắc chắn rằng có một giải pháp hiệu quả hơn.

Answer 4

Điều tốt nhất tôi có thể làm là tạo một số Map từ dữ liệu chưa phân loại và sử dụng tra cứu bản đồ (về cơ bản có thể bắt đầu bằng đề xuất trước đó). Mã này trông giống như:

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

Hoặc, nếu có một khả năng bỏ lỡ băm:

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

Đó là O(n) trong thời gian *, nhưng bạn đang trao đổi thời gian cho không gian, vì nó sử dụng O(n) không gian.

Đối với một phiên bản hơi phức tạp hơn, để xử lý các giá trị bị mất, hãy thử:

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() 

Nếu đó là một cơ sở dữ liệu MongoDB ở nơi đầu tiên, bạn có thể lấy tốt hơn tài liệu trực tiếp từ cơ sở dữ liệu theo chỉ số, vì vậy một cái gì đó như:

index.map(lookupInDB) 

* về mặt kỹ thuật nó O(n log n), như bản đồ bất biến chuẩn Scala là O(log n), nhưng bạn luôn có thể sử dụng một bản đồ có thể thay đổi, đó là O(1)

Answer 5

Trong trường hợp này bạn có thể sử dụng zip-sort-unzip:

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

Btw, nếu bạn có thể, giải pháp tốt hơn sẽ được sắp xếp danh sách bên db sử dụng $orderBy.

Answer 6

Ok.

Hãy bắt đầu lại từ đầu. Bên cạnh thực tế bạn đang quét lại danh sách unsorted mỗi lần, đối tượng Seq sẽ tạo, theo mặc định là bộ sưu tập List. Vì vậy, trong foldLeft, bạn đang thêm phần tử vào cuối danh sách mỗi lần và đây là thao tác O(N^2).

Một cải tiến sẽ

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

Nhưng đó vẫn là một thuật toán O(N^2). Chúng ta có thể làm tốt hơn.

Các chức năng sắp xếp sau đây nên làm việc:

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 
} 

Chức năng sắp xếp một danh sách các mục unsorted bởi một chuỗi các chỉ số index nơi key chức năng sẽ được sử dụng để trích xuất các id từ các đối tượng bạn đang cố gắng xắp xếp.

Dòng 1 tạo chỉ mục đảo ngược - ánh xạ từng id đối tượng đến vị trí cuối cùng của nó.

Dòng 2 phân bổ mảng sẽ giữ chuỗi được sắp xếp. Chúng tôi đang sử dụng một mảng vì chúng tôi cần hiệu suất thiết lập vị trí ngẫu nhiên không đổi theo thời gian.

Các vòng lặp bắt đầu tại dòng 3 sẽ đi qua chuỗi các mặt hàng không được phân loại và đặt mỗi mục trong nó có nghĩa là vị trí bằng cách sử dụng positionMapping chỉ số ngược

Line 6 sẽ trở lại mảng chuyển đổi ngầm để một Seq sử dụng WrappedArray wrapper .

Vì chỉ số đảo ngược của chúng tôi là không thay đổi HashMap, tra cứu sẽ mất thời gian liên tục cho các trường hợp thông thường. Xây dựng chỉ số đảo ngược thực tế mất O(N_Index) thời gian trong đó N_Index là kích thước của chuỗi chỉ mục. Duyệt qua chuỗi chưa phân loại mất O(N_Unsorted) thời gian trong đó N_Unsorted là kích thước của chuỗi chưa phân loại.

Vì vậy, độ phức tạp là O(max(N_Index, N_Unsorted)), điều mà tôi đoán là tốt nhất bạn có thể làm trong hoàn cảnh.

Ví dụ cụ thể của bạn, bạn sẽ gọi hàm như sau:

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

Đối với trường hợp thực tế, nó có lẽ sẽ là như thế này:

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

Answer 7

này có thể không chính xác bản đồ để trường hợp sử dụng của bạn, nhưng nhân viên của Google có thể tìm thấy điều này hữu ích:

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)