Mengurutkan algoritma untuk Excel / SharedStrings

Di Excel, mereka 'kompres' string ke pemetaan numerik (meskipun saya tidak yakin bahwa kata kompres benar dalam kasus ini). Berikut ini contoh yang ditunjukkan di bawah ini:

Meskipun ini membantu mengurangi keseluruhan ukuran file dan jejak memori, bagaimana cara Excel melakukan pengurutan pada bidang string? Apakah setiap string perlu melalui pemetaan pencarian: dan jika demikian, bukankah itu akan sangat meningkatkan biaya / memperlambat melakukan pengurutan pada bidang string (bagaimana jika ada nilai 1M, pencarian kunci 1M tidak akan sepele). Dua pertanyaan tentang ini:

1. Apakah string bersama digunakan dalam aplikasi Excel itu sendiri, atau hanya saat menyimpan data?
2. Apa yang akan menjadi contoh algoritma untuk mengurutkan di lapangan? Bahasa apa pun baik-baik saja (c, c #, c ++, python).

Saya tidak dapat menemukan bagaimana tepatnya Excel menyimpan sel dengan SharedStringTableelemen dalam memori saat runtime, tetapi menyimpannya sebagai indeks item SharedStringTablemembutuhkan hanya satu dereferensi tambahan untuk mengaksesnya, dengan asumsi bahwa elemen disimpan sebagai array. Jadi tebakan saya adalah begini caranya. Itu adalah cara paling sederhana dan satu-satunya cara untuk membuatnya lebih cepat adalah memiliki representasi runtime yang SharedStringTablesudah diurutkan berdasarkan elemen. Dalam kasus semacam itu, menyortir menurut indeks sama dengan menyortir berdasarkan nilainya. Pendekatan itu, bagaimanapun, membuat operasi penyisipan mahal seperti ketika string baru dimasukkan ke tengah tabel semua indeks lebih besar dari yang seharusnya bertambah dan jumlah sel-sel tersebut dalam dokumen bisa sangat besar, hingga semua sel mengacu pada SharedStringTable.

Jika sel berisi indeks yang sama seperti dalam file, di sini adalah bagaimana seseorang akan mengurutkan sel yang diwakili oleh columnValuevektor berdasarkan string yang mereka tunjuk untuk disimpan dalam sharedStringsvektor (dalam C ++ karena Anda mengatakan tidak ada perbedaan) dengan biaya 2 referensi tambahan per operasi perbandingan:

// sort indexes from columnValue based on comparing values in sharedStrings
sort(columnValue.begin(), columnValue.end(), 
     [&sharedStrings](size_t i1, size_t i2){return sharedStrings[i1] < sharedStrings[i2];});

Itu tidak di OP, tetapi SharedStringTableoperasi pencarian sebaliknya lambat dan caching elemen ke dalam kamus membantu.

Microsoft Excel Shared Strings Table

Tabel string bersama adalah dan standar Open XML, sebagaimana ditentukan oleh standar ISO - ISO / IEC 29500-1: 2016 (E)

Definisi resmi dari string Bersama (dikutip dari dokumen ISO)

Tabel String Bersama

Nilai string dapat disimpan langsung di dalam elemen sel spreadsheet; Namun, menyimpan nilai yang sama di dalam beberapa elemen sel dapat menghasilkan Bagian lembar kerja yang sangat besar, mungkin mengakibatkan penurunan kinerja. Shared String Table adalah daftar nilai string yang diindeks, dibagikan di seluruh buku kerja, yang memungkinkan implementasi menyimpan nilai hanya sekali.

Standar ISO pada String Bersama dapat diunduh dari

https://standards.iso.org/ittf/PubliclyAvailableStandards/c071691_ISO_IEC_29500-1_2016.zip

Jawaban untuk pertanyaan tentang topik ini

Pertanyaan 1: Apakah string bersama digunakan dalam aplikasi Excel itu sendiri, atau hanya ketika menyimpan data?

Jawaban: String bersama hanya digunakan oleh Excel pada saat menyimpan dokumen, yaitu IE, hanya untuk tujuan menyimpan spreadsheet sebagai file pada penyimpanan.

Namun, ketika file dibuka untuk ditampilkan, sel-sel diisi dengan nilai string aktual yang ditarik dari tabel string bersama.

-

Pertanyaan 2: Apa yang akan menjadi contoh algoritma untuk mengurutkan di lapangan? Bahasa apa pun baik-baik saja (c, c #, c ++, python).

Jawab: Untuk aplikasi seperti Excel, saya kira variasi khusus kepemilikan Quick sort adalah algoritma yang paling mungkin digunakan untuk mengurutkan nilai string.

Excel memiliki batas 1.048.576 baris. Untuk ukuran ini, Quick sort jelas merupakan pemenang. Pengurutan cepat dapat menghasilkan hasil yang sangat efisien untuk kumpulan data sebesar ini.

Berikut ini tautan ke penerapan Quick Sort di C ++ untuk menyortir string:

http://www.cplusplus.com/forum/beginner/101599/