Menyeret dan menjatuhkan item dalam daftar adalah fitur populer di aplikasi modern, yang kehadirannya hanya akan menyenangkan pengguna. Namun, ketika menerapkan fungsi seperti itu, Anda perlu mencoba untuk tidak menginjak pengoptimalan yang buruk: sejumlah besar elemen, perhitungan ulang posisi setiap kali, dan jika ada beberapa bagian dalam daftar, maka ketika menyeret antar bagian, Anda kemungkinan besar perlu menerapkan logika tambahan. Bagaimana agar tidak terkena dahi, mengurangi jumlah perhitungan, dan bagaimana lexorangs akan membantu kita dengan ini - baca di bawah potongan.
Mari kita definisikan masalahnya
Jadi, Anda telah memutuskan untuk menambahkan fungsionalitas seret dan lepas ke aplikasi Anda. Jadi, Anda perlu mengurutkan elemennya entah bagaimana, jika tidak ada gunanya menyeret dan menjatuhkan. Dan apa hal pertama yang terlintas dalam pikiran?
Posisi
Posisi biasa yang biasa-biasa saja. Angka-angka yang sama dari 1 hingga tak terbatas (tidak juga). Sangat mudah dan nyaman untuk bekerja dengannya, elemen-elemen diurutkan tanpa masalah. Sekilas, semuanya baik-baik saja. Sangat bagus untuk sebagian besar aplikasi, inilah yang Anda butuhkan.
Lalu, apa yang salah dengan posisi numerik?
Masalahnya terletak pada operasi terkait. Perlu menyuntikkan elemen antara elemen kedua dan ketiga? Kami menggeser semuanya maju satu per satu, mulai dari elemen ketiga, sambil tidak lupa memperbarui data dalam database. Melakukan operasi seperti itu sekali tidak terlihat sulit, tetapi operasi ini akan dilakukan cukup sering.
Operasi lain yang bermasalah adalah memperbarui data di server. Memperbarui tugas - Anda harus mengirim pembaruan semua tugas yang terkena dampak ke server. Server, pada gilirannya, harus mengirimkan pembaruan ini kepada semua orang yang "berlangganan" ke daftar tugas. Semakin sering pengguna mengubah urutan tugas dalam daftar, semakin banyak data harus dikirim ke server, dan semakin banyak data yang harus dikirim server ke klien.
Ternyata ketika menyeret satu tugas, kami tidak hanya akan mengubah posisi sejumlah besar elemen, tetapi juga mengirimkannya ke server, yang kemudian akan mengirimkannya ke pengguna lain.
Kesimpulan: Saya menginginkan sesuatu yang lebih optimal
Opsi solusi
Ketika kami di perusahaan menghadapi masalah serupa, solusi pertama yang mungkin adalah algoritma berikut: untuk semua elemen kami akan menempatkan beberapa posisi standar pada interval (langkah) yang sama. Jadi, elemen pertama akan memiliki posisi 1, dan yang kedua - 1000. Ketika pengguna ingin menyeret sesuatu di antara dua elemen ini, kami menghitung posisi rata-rata - (1000 + 1) / 2 = ~ 500. Demikian seterusnya dan seterusnya.
Mengapa opsi ini buruk, saya pikir Anda langsung menebak. Kami terbatas dalam jumlah langkah yang dapat diambil. Itu antara 1 dan 1000 - 500. Antara 1 dan 500 - 250. Kemudian 125 ... dan akhirnya tidak ada ruang. Meningkatkan langkah tidak menyelesaikan masalah ini.
Bisakah kita menggunakan angka pecahan?
Tidak, angka pecahan tidak memperbaiki masalah, tetapi hanya menunda saat kemunculannya.
Setelah berpikir dan mencari-cari di Google, kami menemukan laporan tentang bagaimana lexorang digunakan di Jira (Lexorank, report ).
Mereka didasarkan pada tiga hal:
1 - mudah untuk mengurutkan string dalam urutan abjad
2 - Anda dapat menemukan string tengah antara dua string (tidak selalu, dan ini tidak begitu mudah lagi)
3 - Anda tidak dapat menemukan yang tengah? Mari kita gunakan ember (terdengar aneh, ya).
Dengan menyortir semuanya jelas, kita langsung ke titik nomor 2.
Ada huruf dalam alfabet bahasa Inggris di "a" dan "c", dan di antara mereka, jelas, "b". Tetapi bagaimana menemukan "b" ini secara matematis?
Mari kita kurangi dari kode huruf "c" kode huruf "a", kita dapatkan 2 ("c" = 143, "a" = 141). Masih membagi hasil menjadi dua. Mendapat 1. Memang, jika kita menambahkan satu ke kode "a", kita mendapatkan kode huruf "b".
Kombinasi huruf bahasa Inggris disebut lexorang.
Situasi ketika tidak ada ruang di antara dua baris, mereka juga memiliki tempat untuk menjadi, dan saya sudah menulis bahwa ember digunakan untuk menyelesaikannya.
Ember adalah label sebelum peringkat , terlihat seperti ini: "0 | aaa". Di sini 0 adalah nomor ember. Ketika tidak ada ruang yang tersisa, elemen-elemen dipindahkan dari satu ember ke yang lain, dan label-label tersebut disusun kembali secara berurutan. Itu semua keajaiban!
Bagaimana kami memanfaatkannya
Tidak dikatakan dengan tepat (lebih tepatnya, kami hanya tidak menemukan) betapa mudah dan tidak sulitnya menemukan garis tengah di antara keduanya. Jadi kami tegang dan menemukan ini. Mari kita langsung mencontohkan.
Mari kita ambil dua baris: "aa" dan "cc" dan temukan garis tengah di antara mereka.
Setelah dikurangi dengan simbol, seperti di atas, kita mendapatkan angka 11. Tapi apa yang harus dilakukan selanjutnya? Anda mungkin berpikir Anda hanya perlu menambahkan hasilnya ke baris "aa". Di sini string "bb" akan benar-benar berubah, terletak di antara "aa" dan "cc", tetapi algoritme akan salah, dan sekarang kita akan melihat alasannya.
Mari kita pikirkan seperti apa bentuknya? "Aa", "cc", "11". Semacam sistem angka. Tentang apa? Dan pada tanggal 26! Mengapa? Karena alfabet bahasa Inggris memiliki 26 huruf. Jadi begitu.
Diperlukan untuk menerjemahkan hasilnya, "11", dari sistem bilangan 26-ary ke dalam sistem bilangan 10-ary yang biasa.
Rumusnya cukup sederhana:
X = y 0 + y 1 * ukuran + y 2 * ukuran ^ 2 ... y n * ukuran ^ (n-1)
Di sini ukuran merupakan "ukuran" dari sistem angka (dalam hal ini, ukuran = 26)
y n - angka ke-n di sebelah kanan.
Mari kita mengingat rumus ini, sebagai contoh, rumus 1 , masih akan berguna bagi kita.
Kami mengganti angka-angka kami dan inilah yang kami dapatkan: 2 + 2 * 26 = 54. Sekarang kita tahu berapa banyak karakter yang berada di antara garis "aa" dan "cc". Tapi kita perlu mengambil rata-rata di antara keduanya. Kami membagi 54 dengan 2, kami mendapatkan 27. Tetap hanya untuk menambahkan hasil kami dengan benar ke kode "aa".
Bagaimana cara melakukannya? Pertama, kami mencari tahu berapa banyak untuk ditambahkan ke karakter pertama (kanan). Untuk melakukan ini, kita mendapatkan sisa pembagian 27 dengan 26. Ternyata 1. Tambahkan 1 ke "a" - Anda mendapatkan huruf "b".
Sekarang kita perlu memikirkan bagaimana mencari tahu berapa banyak karakter untuk menggeser karakter kedua.
Di sini rumus berikut akan membantu kita:
X = Y / ukuran ^ (n-1) % ukuran
Dengan rumus ini, kita dapat mengetahui berapa banyak yang perlu ditambahkan ke tempat tertentu (karakter, ditentukan menggunakan n).
Mengganti semua yang ada di sana, kita dapatkan (n = 2): (27/26)% 26 = 1. Tambahkan. Kami mendapatkan hasil akhir "bb".
Tidak begitu sulit untuk mengimplementasikan algoritma dalam bahasa pemrograman apa pun ketika Anda tahu persis cara kerjanya. Di bawah ini saya telah menambahkan implementasi algoritma di Dart (aplikasi di mana masalah ini terjadi ditulis dalam Flutter).
Implementasi kami untuk menemukan baris 'tengah'
String getRankBetween({@required String firstRank, @required String secondRank}) {
assert(firstRank.compareTo(secondRank) < 0, "First position must be lower than second. Got firstRank $firstRank and second rank $secondRank");
/// Make positions equal
while (firstRank.length != secondRank.length) {
if (firstRank.length > secondRank.length)
secondRank += "a";
else
firstRank += "a";
}
var firstPositionCodes = [];
firstPositionCodes.addAll(firstRank.codeUnits);
var secondPositionCodes = [];
secondPositionCodes.addAll(secondRank.codeUnits);
var difference = 0;
for (int index = firstPositionCodes.length - 1; index >= 0; index--) {
/// Codes of the elements of positions
var firstCode = firstPositionCodes[index];
var secondCode = secondPositionCodes[index];
/// i.e. ' a < b '
if (secondCode < firstCode) {
/// ALPHABET_SIZE = 26 for now
secondCode += ALPHABET_SIZE;
secondPositionCodes[index - 1] -= 1;
}
/// formula: x = a * size^0 + b * size^1 + c * size^2
final powRes = pow(ALPHABET_SIZE, firstRank.length - index - 1);
difference += (secondCode - firstCode) * powRes;
}
var newElement = "";
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
} else {
difference ~/= 2;
var offset = 0;
for (int index = 0; index < firstRank.length; index++) {
/// formula: x = difference / (size^place - 1) % size;
/// i.e. difference = 110, size = 10, we want place 2 (middle),
/// then x = 100 / 10^(2 - 1) % 10 = 100 / 10 % 10 = 11 % 10 = 1
final diffInSymbols = difference ~/ pow(ALPHABET_SIZE, index) % (ALPHABET_SIZE);
var newElementCode = firstRank.codeUnitAt(
secondRank.length - index - 1) + diffInSymbols + offset;
offset = 0;
/// if newElement is greater then 'z'
if (newElementCode > 'z'.codeUnits.first) {
offset++;
newElementCode -= ALPHABET_SIZE;
}
newElement += String.fromCharCode(newElementCode);
}
newElement = newElement
.split('')
.reversed
.join();
}
return newElement;
}
Tapi itu belum semuanya
Bagaimanapun, itu tidak semua untuk kita. Kami menambahkan fitur ini ke aplikasi yang sudah dirilis, sehingga diperlukan migrasi. Menulis migrasi untuk SQL tidak ada masalah, tetapi menghitung peringkat standar tidak lagi begitu mudah. Tetapi, mengetahui bagaimana baris tengah berada, menjadi tidak sulit untuk melakukan ini. Algoritma akan menjadi sebagai berikut:
- atur awal dan akhir interval (bagi kami ini adalah "aaa" dan "zzz", masing-masing)
- kami menghitung berapa banyak kombinasi karakter yang berbeda di antara baris, di sini rumus 1 akan membantu kami
- sekarang kami membagi hasilnya dengan jumlah elemen maksimum yang mungkin ada dalam daftar
- jadi, kita memiliki langkah, ada posisi awal, tetap hanya menambahkan langkah ke posisi awal, mendapatkan peringkat, lalu menambahkan langkah ke peringkat ini, mendapatkan peringkat baru, lalu menambahkan langkah lagi, dan seterusnya
Itu sama di Dart. parameter forNumOfTasks bertanggung jawab untuk berapa banyak posisi yang Anda dapatkan. Jika Anda meletakkan posisi untuk daftar di mana hanya ada tiga elemen sekarang, tidak masuk akal untuk menghitung posisi untuk seluruh daftar (dengan 50, 100 atau yang lainnya)
Implementasi kami untuk menemukan peringkat 'default'
/// modify field forNumOfTasks to get certain number of positions
List‹String› getDefaultRank({int forNumOfTasks = TASK_FOR_PROJECT_LIMIT_TOTAL}) {
final startPos = START_POSITION;
final endPos = END_POSITION;
final startCode = startPos.codeUnits.first;
final endCode = endPos.codeUnits.first;
final diffInOneSymb = endCode - startCode;
/// x = a + b * size + c * size^2
final totalDiff = diffInOneSymb + diffInOneSymb * ALPHABET_SIZE + diffInOneSymb * ALPHABET_SIZE * ALPHABET_SIZE;
/// '~/' – div without remainder
final diffForOneItem = totalDiff ~/ (TASK_FOR_PROJECT_LIMIT_TOTAL + 1);
/// x = difference / size^(place - 1) % size
final List‹int› diffForSymbols = [
diffForOneItem % ALPHABET_SIZE,
diffForOneItem ~/ ALPHABET_SIZE % ALPHABET_SIZE,
diffForOneItem ~/ (pow(ALPHABET_SIZE, 2)) % ALPHABET_SIZE
];
List‹String› positions = [];
var lastAddedElement = startPos;
for (int ind = 0; ind < forNumOfTasks; ind++) {
var offset = 0;
var newElement = "";
for (int index = 0; index < 3; index++) {
final diffInSymbols = diffForSymbols[index];
var newElementCode = lastAddedElement.codeUnitAt(2 - index) + diffInSymbols;
if (offset != 0) {
newElementCode += 1;
offset = 0;
}
/// 'z' code is 122 if 'll be needed
if (newElementCode > 'z'.codeUnitAt(0)) {
offset += 1;
newElementCode -= ALPHABET_SIZE;
}
final symbol = String.fromCharCode(newElementCode);
newElement += symbol;
}
/// reverse element cuz we are calculating from the end
newElement = newElement.split('').reversed.join();
positions.add(newElement);
lastAddedElement = newElement;
}
positions.sort();
positions.forEach((p) => print(p));
return positions;
}
Fuuuuh, apakah kamu lelah? Bagian tersulit telah usai, sangat sedikit yang tersisa!
Kami tidak terlalu menyukai ide ember. Secara obyektif, dia baik. Namun kami tidak menyukai gagasan memiliki algoritme "pemulihan": jika posisi selesai, pulihkan dengan keranjang! Jadi, tidak ada ember. Namun, pangkatnya tidak terbatas, yang berarti bahwa sesuatu harus ditemukan.
Dan kami datang dengan
Jika tidak ada ruang yang tersisa di antara garis, maka kami memutuskan untuk hanya menambahkan huruf tengah alfabet Inggris ("n") ke batas bawah. Itu jika kita ingin menempelkan elemen antara "aa" dan "ab", kita mendapatkan "aa", "aan" dan "ab". Karena fakta bahwa string diurutkan berdasarkan elemen dari kiri ke kanan, memperpanjang string tidak akan merusak sortir. Tetapi kami memiliki tempat untuk elemen baru, dan ini tanpa algoritma pemulihan.
Sepotong kode ini juga dapat ditemukan dalam algoritma untuk menemukan garis tengah.
Sepotong kode dengan penambahan karakter 'menengah'
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}
Ringkasan
Bagi kami Lexorangs adalah alat pengindeksan yang sangat baik, yang penggunaannya mengoptimalkan pekerjaan dengan database dan server: ketika mengubah urutan tugas, hanya satu tugas yang diubah yang perlu diperbarui.
Bagikan pendapat Anda tentang lexorangs dan pemikiran apa yang Anda miliki tentang menyelesaikan masalah seperti itu.
Nah, untuk semua pembaca Habr, kami mengusulkan untuk mengevaluasi hasil yang kami dapatkan. Dan juga mengambil daftar "Kode Penulis Habr" yang bermanfaat .
Terima kasih atas perhatian anda!