👩‍🎤 ✨ 🔼 Lexorangs-它们是什么以及如何使用它们对列表进行有效排序 🤼 💛 💟

在本文中，我将解释Lexorangs是什么，它们在Jira中的用法，以及我们如何使用它们在移动应用程序中有效地对列表进行排序和拖放项目。

拖放列表中的项目是现代应用程序中的流行功能，其存在只会使用户感到满意。但是，在实现这种功能时，您需要尽量不要踩踏糟糕的优化流程：大量元素，每次重新计算位置，并且如果列表中有多个部分，那么在各部分之间拖动时，您很可能需要实现其他逻辑。如何不被额头击中，减少计算次数，以及lexorangs将如何帮助我们-请仔细阅读。

让我们定义问题

因此，您决定向您的应用程序添加拖放功能。因此，您需要以某种方式对元素进行排序，否则拖放毫无意义。想到的第一件事是什么？

职位

最常见的不起眼的职位。从1到无穷大的那些相同数字（不是真的）。使用它们很容易和方便，对元素进行排序没有问题。乍一看，一切都很好。非常好，对于大多数应用程序，这就是您所需要的。

那么，数字位置有什么问题呢？

问题出在相关的操作上。是否需要在第二和第三元素之间注入元素？从第三个元素开始，我们将所有内容向前移动一位，同时不要忘记更新数据库中的数据。一次执行这样的操作看起来并不困难，但是将经常执行该操作。

另一个有问题的操作是更新服务器上的数据。更新了任务-您需要将所有受影响的任务的更新发送到服务器。反过来，服务器应将此更新发送给“订阅”任务列表的每个人。用户更改列表中任务顺序的频率越高，必须将更多数据发送到服务器，并且服务器必须将更多数据发送到客户端。

事实证明，当拖动一个任务时，我们不仅会更改大量元素的位置，还将它们发送到服务器，然后服务器会将它们发送给其他用户。

结论：我想要更好的东西

解决方案选项

当我们公司中遇到类似问题时，第一个可能的解决方案是以下算法：对于所有元素，我们将以相等的间隔（步骤）放置一些标准位置。因此，第一个元素的位置为1，第二个元素的位置为1000。当用户想要在这两个元素之间拖动某些内容时，我们将计算平均位置-（1000 + 1）/ 2 =〜500。等等等等。

为什么这个选项不好，我想您马上就猜到了。我们可以采取的步骤数量有限。那些。在1到1000-500之间。在1到500-250之间。然后125 ...最终将没有空间。增加步骤不能解决此问题。

我们可以使用分数吗？

不，分数不能解决问题，而只会延迟问题的出现。

经过一番思考和谷歌搜索，我们看到了一份有关在Jira中如何使用lexorangs的报告（Lexorank，report）。

它们基于三件事：

1-可以容易地按字母顺序对字符串进行排序

2-您可以找到两个字符串之间的中间字符串（并不总是如此，这不再那么容易了）

3-您找不到中间的字符串吗？让我们使用一个存储桶（听起来很奇怪，是的），

对所有内容进行清晰的排序后，我们直接转到第2点。

英语字母中的字母分别在“ a”和“ c”中，并且在它们之间显然是“ b”。但是如何在数学上找到这个“ b”呢？

让我们从字母“ c”的代码中减去字母“ a”的代码，得出2（“ c” = 143，“ a” = 141）。仍然需要将结果分成两半。得到了1。的确，如果我们在代码“ a”上加一个，则得到字母“ b”的代码。

英文字母的组合称为lexorang，

在两行之间没有空格的情况下，也有一个地方，我已经写过用桶来解决它们。

值区是等级之前的标签，它看起来像这样：“ 0 | aaa”。这里0是存储桶编号。如果没有剩余空间，则将元素从一个存储桶移至另一个存储桶，并按顺序重新排列标签。这就是所有的魔力！

我们如何利用它

并没有确切地说（相反，我们只是没有找到）找到两者之间的中间线是多么容易和轻松。因此，我们紧张并提出了这个建议。让我们立即跳入一个例子。

让我们采用两行：“ aa”和“ cc”并找到它们之间的中间线。

如上用符号减法后，得到数字11。但是下一步该怎么做？您可能会认为您只需要将结果添加到“ aa”行即可。这里的字符串“ bb”确实会出现，位于“ aa”和“ cc”之间，但是算法不正确，现在我们将了解原因。

让我们考虑一下它的外观吗？ “ Aa”，“ cc”，“ 11”。某种数字系统。什么？还有26号！为什么？因为英文字母有26个字母。就是这样了。

必须将结果“ 11”从26进制数字系统转换为通常的10进制数字系统。

公式非常简单：

X = y ₀ + y ₁ *大小+ y ₂ *大小^ ² ... y _n *大小^ ^（n-1）

这里，大小是数字系统的“大小”（在这种情况下，大小= 26）

y _n -右边的第n个数字

让我们记住该公式，例如，公式1，它将仍然对我们有用。

我们用数字代替，这就是我们得到的：2 + 2 * 26 =54。现在我们知道“ aa”和“ cc”行之间有多少个字符。但是我们需要取两者之间的平均值。我们将54除以2，得到27。它仅是为了将结果正确添加到“ aa”代码中。

怎么做？首先，我们找出要添加到第一个（右侧）字符的数量。为此，我们得到27除以26的余数。结果是1.将“ a”加1-得到字母“ b”。

现在我们需要考虑如何找出要移动第二个字符的字符数。

在这里，以下公式将为我们提供帮助：

X = Y / size ^ ^（n-1）％size

通过此公式，我们可以找到需要添加到特定位置的多少（字符，使用n指定）。

替换那里的所有内容，我们得到（n = 2）：（27/26）％26 =1。加。我们得到最终结果“ bb”。

当您确切地知道算法的工作原理时，用任何一种编程语言来实现一个算法都不是那么困难。下面，我在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将帮助我们
现在我们将结果除以列表中元素的最大数量
因此，我们有一个步骤，有一个初始位置，它仅是向初始位置添加一个步骤，获得一个等级，然后向该等级添加一个步骤，获得一个新的等级，然后再次添加一个步骤，依此类推

Dart上也一样。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的看法以及您对解决此类问题的想法。

好吧，对于Habr的所有读者，我们建议评估我们得到的结果。并且还选择了“哈勃作者代码”的有用列表。

感谢您的关注！

Lexorangs-它们是什么以及如何使用它们对列表进行有效排序

让我们定义问题

职位

解决方案选项

但这还不是全部

摘要

More articles: