يعد سحب العناصر وإفلاتها في القائمة ميزة شائعة في التطبيقات الحديثة ، وسيسعد وجودها المستخدمين فقط. ومع ذلك ، عند تنفيذ مثل هذه الوظيفة ، تحتاج إلى محاولة عدم المضي في تحسين أمثل: عدد كبير من العناصر ، وإعادة حساب الموضع في كل مرة ، وإذا كان هناك أيضًا عدة أقسام في القائمة ، فعند السحب بين الأقسام ، على الأرجح ، يجب تنفيذ منطق إضافي. كيف لا تضرب في الجبين ، وتقلل من عدد الحسابات ، وكيف ستساعدنا lexorangs في ذلك - اقرأ تحت القطع.
دعونا نحدد المشكلة
لذا ، قررت إضافة وظيفة السحب والإفلات إلى تطبيقك. لذلك ، تحتاج إلى فرز العناصر بطريقة أو بأخرى ، وإلا فلا فائدة من السحب والإسقاط. وما هو أول شيء يتبادر إلى الذهن؟
البنود
المواقف الأكثر شيوعا غير ملحوظة. هذه الأرقام نفسها من 1 إلى ما لا نهاية (ليس في الحقيقة). من السهل والعمل معهم ، يتم فرز العناصر دون مشاكل. للوهلة الأولى ، كل شيء على ما يرام. جيد جدًا أنه بالنسبة لمعظم التطبيقات ، هذا ما تحتاجه.
إذن ، ما هو الخطأ في الموقف الرقمي؟
تكمن المشكلة في العمليات المرتبطة. هل تحتاج إلى حقن عنصر بين العنصرين الثاني والثالث؟ ننقل كل شيء إلى الأمام واحدًا ، بدءًا من العنصر الثالث ، مع عدم نسيان تحديث البيانات في قاعدة البيانات. لا يبدو تنفيذ هذه العملية مرة واحدة صعبًا ، ولكن سيتم تنفيذ هذه العملية في كثير من الأحيان.
عملية إشكالية أخرى هي تحديث البيانات على الخادم. تحديث المهمة - تحتاج إلى إرسال تحديث لجميع المهام المتأثرة إلى الخادم. يجب على الخادم ، بدوره ، إرسال هذا التحديث إلى كل "المشترك" في قائمة المهام. كلما قام المستخدمون بتغيير ترتيب المهام في القائمة في كثير من الأحيان ، يجب إرسال المزيد من البيانات إلى الخادم ، والمزيد من البيانات التي يجب أن يرسلها الخادم إلى العملاء.
اتضح أنه عند سحب مهمة واحدة ، لن نقوم فقط بتغيير مواضع عدد كبير من العناصر ، ولكن أيضًا نرسلها إلى الخادم ، والتي سترسلها بعد ذلك إلى مستخدمين آخرين.
خاتمة: أريد شيئًا أكثر مثالية
خيارات الحل
عندما واجهنا في الشركة مشكلة مماثلة ، كان أول حل ممكن هو الخوارزمية التالية: لجميع العناصر ، سنضع بعض المواقف القياسية على فترات متساوية (خطوات). لذلك ، سيكون للعنصر الأول موضع 1 ، والعنصر الثاني - 1000. عندما يريد المستخدم سحب شيء ما بين هذين العنصرين ، فإننا نحسب متوسط المركز - (1000 + 1) / 2 = ~ 500. وهلم جرا وهكذا دواليك.
لماذا هذا الخيار سيئ ، أعتقد أنك خمنت على الفور. نحن محدودون في عدد الخطوات التي يمكن اتخاذها. أولئك. بين 1 و 1000 - 500. بين 1 و 500 - 250. ثم 125 ... وفي النهاية لن يكون هناك مكان. زيادة الخطوة لا يحل هذه المشكلة.
هل يمكننا استخدام الأرقام الكسرية؟
لا ، فالأرقام الكسرية لا تصلح المشكلة ، ولكنها تؤخر لحظة ظهورها فقط.
بعد قليل من التفكير و googling ، توصلنا إلى تقرير حول كيفية استخدام lexorangs في Jira ( تقرير Lexorank ، ).
وهي تستند إلى ثلاثة أشياء:
1 - من السهل فرز السلاسل بالترتيب الأبجدي
2 - يمكنك العثور على السلسلة الوسطى بين سلسلتين (ليس دائمًا ، وهذا ليس سهلاً بعد الآن)
3 - ألا يمكنك العثور على السطر الأوسط؟ دعنا نستخدم دلوًا (يبدو غريبًا ، نعم)
مع فرز كل شيء واضح ، ننتقل مباشرة إلى النقطة رقم 2.
هناك أحرف في الأبجدية الإنجليزية في "أ" و "ج" ، وبينهم ، من الواضح ، "ب". ولكن كيف يمكن إيجاد هذا "ب" رياضياً؟
لنطرح فقط من رمز الحرف "c" رمز الحرف "a" ، نحصل على 2 ("c" = 143، "a" = 141). يبقى لتقسيم النتيجة إلى النصف. حصلت على 1. في الواقع ، إذا أضفنا واحدًا إلى الرمز "a" ، نحصل على رمز الحرف "b".
يسمى مزيج من الأحرف الإنجليزية lexorang.
الحالات التي لا توجد فيها مسافة بين سطرين ، وهناك أيضًا مكان يمكن أن أقوم به ، وقد كتبت بالفعل أن الدلاء تستخدم لحلها.
الدلو هو الملصق قبل الرتبة ، يبدو كالتالي: "0 | aaa". هنا 0 هو رقم الجرافة. في حالة عدم وجود مساحة متبقية ، يتم نقل العناصر من دلو إلى آخر ، ويتم إعادة ترتيب التسميات بالترتيب. هذا كل السحر!
كيف استفدنا منه
لا يقال بالضبط (بدلاً من ذلك ، لم نجد فقط) مدى سهولة العثور على الخط الأوسط بين الاثنين بسهولة. لذلك قمنا بالتوتر وخرجنا بهذا. دعنا نغرق على سبيل المثال.
لنأخذ خطين: "aa" و "cc" ونجد الخط الأوسط بينهما.
بعد الطرح بالرمز ، على النحو الوارد أعلاه ، نحصل على الرقم 11. ولكن ماذا نفعل بعد ذلك؟ قد تعتقد أنك تحتاج فقط لإضافة النتيجة إلى سطر "aa". هنا ستظهر السلسلة "bb" بالفعل ، وتقع بين "aa" و "cc" ، لكن الخوارزمية ستكون غير صحيحة ، والآن سنرى السبب.
دعونا نفكر في ما يبدو؟ "أأ" ، "سم مكعب" ، "11". نوع من نظام الأعداد. على ماذا؟ وفي السادس والعشرين! لماذا ا؟ لأن الأبجدية الإنجليزية تتكون من 26 حرفًا. هذا كل ما في الأمر.
من الضروري ترجمة النتيجة "11" من نظام الأرقام 26-ary إلى نظام الأرقام 10-ary المعتاد.
الصيغة بسيطة للغاية:
X = y 0 + y 1 * size + y 2 * size ^ 2 ... y n * size ^ (n-1)
هنا الحجم هو "حجم" نظام الأرقام (في هذه الحالة ، الحجم = 26)
y n - رقم n على اليمين
دعونا نتذكر هذه الصيغة لأنها ، على سبيل المثال ، الصيغة 1 ، ستظل مفيدة لنا.
نستبدل أرقامنا وهذا ما نحصل عليه: 2 + 2 * 26 = 54. الآن نعرف عدد الأحرف بين السطر "aa" و "cc". لكننا بحاجة إلى أخذ المتوسط بين الاثنين. نقسم 54 على 2 ، نحصل على 27. يبقى فقط لإضافة النتيجة بشكل صحيح إلى رموز "aa".
كيف افعلها؟ أولاً ، اكتشفنا مقدار ما يمكن إضافته إلى الحرف الأول (الأيمن). للقيام بذلك ، نحصل على الباقي من قسمة 27 على 26. اتضح 1. أضف 1 إلى "أ" - تحصل على الحرف "ب".
الآن نحن بحاجة إلى التفكير في كيفية معرفة عدد الأحرف لتغيير الشخصية الثانية.
هنا ستساعدنا الصيغة التالية:
X = Y / size ^ (n-1) ٪ size باستخدام
هذه الصيغة ، يمكننا معرفة مقدار ما يجب إضافته إلى مكان معين (يتم تحديد الحرف باستخدام n).
استبدال كل شيء هناك نحصل على (ن = 2): (27/26)٪ 26 = 1. إضافة. نحصل على النتيجة النهائية "ب ب".
ليس من الصعب تنفيذ خوارزمية بأي لغة برمجة عندما تعرف بالضبط كيف تعمل. لقد أضفت أدناه تنفيذ الخوارزمية في Dart (التطبيق الذي حدثت فيه هذه المشكلة مكتوب في Flutter).
تطبيقنا لإيجاد الصف "الأوسط"
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;
}
ولكن هذا ليس كل شيء
على أي حال ، لم يكن كل شيء بالنسبة لنا. أضفنا هذه الميزة إلى تطبيق تم إصداره بالفعل ، لذلك كانت هناك حاجة إلى الترحيل. لا توجد مشكلة في كتابة عمليات الترحيل لـ SQL ، ولكن لم يعد حساب الرتب القياسية بهذه السهولة. ولكن ، مع معرفة كيفية وضع الصف الأوسط ، يصبح من الصعب القيام بذلك. ستكون الخوارزمية كما يلي:
- تعيين بداية الفاصل الزمني ونهايته (بالنسبة لنا هذه هي "aaa" و "zzz" ، على التوالي)
- نحسب عدد مجموعات الشخصيات المختلفة بين السطور ، هنا الصيغة 1 ستساعدنا
- الآن نقسم النتيجة على أكبر عدد ممكن من العناصر في القائمة
- لذلك ، لدينا خطوة ، هناك موضع مبدئي ، يبقى فقط لإضافة خطوة إلى الموضع الأولي ، والحصول على رتبة ، ثم إضافة خطوة إلى هذا الترتيب ، والحصول على رتبة جديدة ، ثم إضافة خطوة مرة أخرى ، وهكذا
إنه نفس الشيء على دارت. تعتبر المعلمة forNumOfTasks مسؤولة عن عدد المواضع التي تحصل عليها. إذا قمت بوضع مواضع لقائمة لا يوجد فيها سوى ثلاثة عناصر الآن ، فمن غير المنطقي حساب المواقف للقائمة بالكامل (بنسبة 50 أو 100 أو أي شيء آخر)
تطبيقنا لإيجاد مراتب "افتراضية"
/// 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 ، هل أنت متعب؟ الجزء الأصعب قد انتهى ، ولم يبق سوى القليل!
لم نحب فكرة الدلو. بموضوعية ، إنها جيدة. لكننا لم نحب فكرة وجود خوارزمية "الاسترداد": إذا انتهت المواضع ، استردها باستخدام الجرافات! لذا ، لا دلاء. ومع ذلك ، فإن الرتب ليست لانهائية ، مما يعني أنه يجب اختراع شيء ما.
وقد توصلنا إلى
أنه إذا لم يكن هناك مسافة متبقية بين السطور ، فقد قررنا ببساطة إضافة الحرف الأوسط من الأبجدية الإنجليزية ("n") إلى الحد السفلي. أولئك. إذا أردنا لصق عنصر بين "aa" و "ab" ، نحصل على "aa" و "aan" و "ab". نظرًا لحقيقة أن السلاسل مرتبة حسب العنصر من اليسار إلى اليمين ، فإن إطالة السلسلة لن تفسد الفرز. ولكن لدينا مكان للعناصر الجديدة ، وهذا بدون أي خوارزميات استرداد.
يمكن أيضًا العثور على هذا الرمز في الخوارزمية للعثور على الخط الأوسط.
قطعة من الكود مع إضافة حرف "متوسط"
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}
ملخص
بدت لنا Lexorangs أداة فهرسة ممتازة ، يعمل استخدامها على تحسين العمل مع قاعدة البيانات والخادم: عند تغيير ترتيب المهام ، يجب تحديث مهمة واحدة تم تغييرها فقط.
شاركنا رأيك حول lexorangs والأفكار التي لديك حول حل مثل هذه المشاكل.
حسنًا ، لجميع قراء حبر ، نقترح تقييم النتيجة التي حصلنا عليها. وأيضا اختيار قائمة مفيدة من "مدونة المؤلف هبر" .
شكرا على انتباهك!