fractional-indexing排序算法
2020-07-19 本文已影响0人
豪爵吸金ing
#define BASE_62_DIGITS "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
#define BASE_95_DIGITS " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
#define BASE_10_DIGITS "0123456789"
std::string midpoint(const std::string &pre, const std::string &next, const std::string &digits) {
std::string a = pre;
std::string b = next;
std::string result = "";
if (!b.empty() && strcmp(a.c_str(), b.c_str()) >= 0)
throw std::string(a + std::string(" >= ") + b);
if (getLastChar(a) == '0' || getLastChar(b) == '0')
throw std::string("trailing zero");
if (!b.empty()) {
// remove longest common prefix. pad `a` with 0s as we
// go. note that we don't need to pad `b`, because it can't
// end before `a` while traversing the common prefix
size_t n = 0;
while ('0' == b.at(n) || (a.length() > n && a.at(n) == b.at(n))) {
n++;
if (b.length() <= n)
break;
}
if (n > 0) {
size_t need_fill_count = n - a.length();
if (need_fill_count > 0)
a += std::string(need_fill_count, '0');
return b.substr(0, n) + midpoint(a.substr(n), b.substr(n), digits);
}
}
size_t digitA = !a.empty() ? digits.find(a.at(0)) : 0;
size_t digitB = !b.empty() ? digits.find(b.at(0)) : digits.size();
if (digitB - digitA > 1) {
size_t midDigit = ceil(0.5*(digitA + digitB));
return std::string(1, digits[midDigit]);
}
else {
// first digits are consecutive
if (!b.empty() && b.length() > 1) {
return b.substr(0, 1);
}
else {
// `b` is null or has length 1 (a single digit).
// the first digit of `a` is the previous digit to `b`,
// or 9 if `b` is null.
// given, for example, midpoint('49', '5'), return
// '4' + midpoint('9', null), which will become
// '4' + '9' + midpoint('', null), which is '495'
if (a.empty()) a = "0";
return digits.at(digitA) + midpoint(a.substr(1), "", digits);
}
}
return result;
}
一些测试用例
BASE_10_DIGITS = "0123456789"
`PASS [ ] 5
PASS 5 ] 8
PASS 8 ] 9
PASS 9 ] 95
PASS 95 ] 98
PASS 98 ] 99
PASS 99 ] 995
PASS 1 2 15
PASS 2 1 !error
PASS [ [ !error
PASS 0 1 !error
PASS 1 10 !error
PASS 11 1 !error
PASS 001 001002 001001
PASS 001 001001 0010005
PASS [ 5 3
PASS [ 3 2
PASS [ 2 1
PASS [ 1 05
PASS 05 1 08
但是问题来了 调用100次 midpoint("", topLayerIndex, BASE_10_DIGITS); 新增100个图层，键的长度也会以线性速度增长。
新增图层1 layer_index :5
新增图层2 layer_index :3
新增图层3 layer_index :2
新增图层4 layer_index :1
新增图层5 layer_index :05
新增图层6 layer_index :03
新增图层7 layer_index :02
新增图层8 layer_index :01
新增图层9 layer_index :005
新增图层10 layer_index :003
新增图层11 layer_index :002
新增图层12 layer_index :001
新增图层13 layer_index :0005
新增图层14 layer_index :0003
新增图层15 layer_index :0002
新增图层16 layer_index :0001
新增图层17 layer_index :00005
新增图层18 layer_index :00003
新增图层19 layer_index :00002
新增图层20 layer_index :00001
新增图层21 layer_index :000005
新增图层22 layer_index :000003
新增图层23 layer_index :000002
新增图层24 layer_index :000001
新增图层25 layer_index :0000005
新增图层26 layer_index :0000003
新增图层27 layer_index :0000002
新增图层28 layer_index :0000001
新增图层29 layer_index :00000005
新增图层30 layer_index :00000003
新增图层31 layer_index :00000002
新增图层32 layer_index :00000001
新增图层33 layer_index :000000005
新增图层34 layer_index :000000003
新增图层35 layer_index :000000002
新增图层36 layer_index :000000001
新增图层37 layer_index :0000000005
新增图层38 layer_index :0000000003
新增图层39 layer_index :0000000002
新增图层40 layer_index :0000000001
新增图层41 layer_index :00000000005
新增图层42 layer_index :00000000003
新增图层43 layer_index :00000000002
新增图层44 layer_index :00000000001
新增图层45 layer_index :000000000005
新增图层46 layer_index :000000000003
新增图层47 layer_index :000000000002
新增图层48 layer_index :000000000001
新增图层49 layer_index :0000000000005
新增图层50 layer_index :0000000000003
新增图层51 layer_index :0000000000002
新增图层52 layer_index :0000000000001
新增图层53 layer_index :00000000000005
新增图层54 layer_index :00000000000003
新增图层55 layer_index :00000000000002
新增图层56 layer_index :00000000000001
新增图层57 layer_index :000000000000005
新增图层58 layer_index :000000000000003
新增图层59 layer_index :000000000000002
新增图层60 layer_index :000000000000001
新增图层61 layer_index :0000000000000005
新增图层62 layer_index :0000000000000003
新增图层63 layer_index :0000000000000002
新增图层64 layer_index :0000000000000001
新增图层65 layer_index :00000000000000005
新增图层66 layer_index :00000000000000003
新增图层67 layer_index :00000000000000002
新增图层68 layer_index :00000000000000001
新增图层69 layer_index :000000000000000005
新增图层70 layer_index :000000000000000003
新增图层71 layer_index :000000000000000002
新增图层72 layer_index :000000000000000001
新增图层73 layer_index :0000000000000000005
新增图层74 layer_index :0000000000000000003
新增图层75 layer_index :0000000000000000002
新增图层76 layer_index :0000000000000000001
新增图层77 layer_index :00000000000000000005
新增图层78 layer_index :00000000000000000003
新增图层79 layer_index :00000000000000000002
新增图层80 layer_index :00000000000000000001
新增图层81 layer_index :000000000000000000005
新增图层82 layer_index :000000000000000000003
新增图层83 layer_index :000000000000000000002
新增图层84 layer_index :000000000000000000001
新增图层85 layer_index :0000000000000000000005
新增图层86 layer_index :0000000000000000000003
新增图层87 layer_index :0000000000000000000002
新增图层88 layer_index :0000000000000000000001
新增图层89 layer_index :00000000000000000000005
新增图层90 layer_index :00000000000000000000003
新增图层91 layer_index :00000000000000000000002
新增图层92 layer_index :00000000000000000000001
新增图层93 layer_index :000000000000000000000005
新增图层94 layer_index :000000000000000000000003
新增图层95 layer_index :000000000000000000000002
新增图层96 layer_index :000000000000000000000001
新增图层97 layer_index :0000000000000000000000005
新增图层98 layer_index :0000000000000000000000003
新增图层99 layer_index :0000000000000000000000002
新增图层100 layer_index :0000000000000000000000001
const std::string INTEGER_ZERO = "a0";
const std::string SMALLEST_INTEGER = "A00000000000000000000000000";
int getIntegerLength(const std::string &head) {
if (head.empty()) {
throw std::string("head.empty()");
}
char h = head.at(0);
if (h >= 'a' && h <= 'z') {
return (int)(h - 'a' + 2);
}
else if (h >= 'A' && h <= 'Z') {
return (int)('Z' - h + 2);
}
else {
throw std::string("Invalid order key head: " + head);
}
}
std::string getIntegerPart(const string & key) {
const int integerPartLength = getIntegerLength(key);
if (integerPartLength > key.length()) {
throw std::string("invalid order key: " + key);
}
return key.substr(0, integerPartLength);
}
void validateOrderKey(const string &key) {
if (key == SMALLEST_INTEGER) {
throw std::string("invalid order key: " + key);
}
// getIntegerPart will throw if the first character is bad,
// or the key is too short. we'd call it to check these things
// even if we didn't need the result
std::string inter_part = getIntegerPart(key);
std::string f = key.substr(inter_part.length());
if (!f.empty() && f.back() == '0') {
throw std::string("invalid order key: " + key);
}
}
void validateInteger(const std::string &inter_part) {
if (inter_part.length() != getIntegerLength(inter_part)) {
throw std::string("invalid integer part of order key: " + inter_part);
}
}
// note that this may return null, as there is a largest integer
std::string incrementInteger(const std::string &src,
const std::string & digits) {
std::string x = src;
validateInteger(x);
const char head = x[0];
x = x.substr(1);
bool carry = true;
for (int i = x.length() - 1; carry && i >= 0; i--) {
size_t d = digits.find(x[i]) + 1;
if (d == digits.length()) {
x[i] = '0';
}
else {
x[i] = digits[d];
carry = false;
}
}
if (carry) {
if (head == 'Z') {
return "a0";
}
if (head == 'z') {
return "";
}
const char h = head + 1;
if (h > 'a') {
x = x + "0";
}
else {
x = x.substr(0, x.length() - 1);
}
return h + x;
}
else {
return head + x;
}
}
std::string decrementInteger(const std::string &src,
const std::string & digits) {
std::string x = src;
validateInteger(x);
const char head = x[0];
x = x.substr(1);
bool borrow = true;
for (int i = x.length() - 1; borrow && i >= 0; i--) {
size_t d = digits.find(x[i]) - 1;
if (d == -1) {
x[i] = digits.back();
}
else {
x[i] = digits.at(d);
borrow = false;
}
}
if (borrow) {
if (head == 'a') {
std::string result = "Z";
result.push_back(digits.back());
return result;
}
if (head == 'A') {
return "";
}
const char h = head - 1;
if (h < 'Z') {
x = x + digits.back();
}
else {
x = x.substr(0, x.length() - 1);
}
return h + x;
}
else {
return head + x;
}
}
std::string generateKeyBetween(const std::string & a, const std::string & b, const std::string & digits)
{
if (!a.empty()) {
validateOrderKey(a);
}
if (!b.empty()) {
validateOrderKey(b);
}
if (!a.empty() && !b.empty() &&
strcmp(a.c_str(), b.c_str()) >= 0) {
throw std::string("generateKeyBetween Error " + a + " >= " + b);
}
if (a.empty() && b.empty()) {
return INTEGER_ZERO;
}
if (a.empty()) {
std::string ib = getIntegerPart(b);
std::string fb = b.substr(ib.length());
if (ib == SMALLEST_INTEGER) {
return ib + midpoint("", fb, digits);
}
return strcmp(ib.c_str(), b.c_str()) < 0 ? ib : decrementInteger(ib, digits);
}
if (b.empty()) {
std::string ia = getIntegerPart(a);
std::string fa = a.substr(ia.length());
std::string i = incrementInteger(ia, digits);
return i.empty() ? ia + midpoint(fa, "", digits) : i;
}
std::string ia = getIntegerPart(a);
std::string fa = a.substr(ia.length());
std::string ib = getIntegerPart(b);
std::string fb = b.substr(ib.length());
if (ia == ib) {
return ia + midpoint(fa, fb, digits);
}
std::string i = incrementInteger(ia, digits);
return strcmp(i.c_str(), b.c_str()) < 0 ? i : ia + midpoint(fa, "", digits);
}
测试用例
`PASS | | a0
PASS | a0 Zz
PASS a0 | a1
PASS a0 a1 a0V
PASS a0V a1 a0l
PASS Zz a0 ZzV
PASS Zz a1 a0
PASS | Y00 Xzzz
PASS bzz | c000
PASS a0 a0V a0G
PASS a0 a0G a08
PASS b125 b129 b127
PASS a0 a1V a1
PASS Zz a01 a0
PASS | a0V a0
PASS | b999 b99
PASS | A00000000000000000000000000 !error
PASS | A000000000000000000000000001 A000000000000000000000000000V
PASS zzzzzzzzzzzzzzzzzzzzzzzzzzy | zzzzzzzzzzzzzzzzzzzzzzzzzzz
PASS zzzzzzzzzzzzzzzzzzzzzzzzzzz | zzzzzzzzzzzzzzzzzzzzzzzzzzzV
添加本人微信EagleAndy
注明QT爱好者，将拉您进QT大佬交流群。
注明SKIA爱好者，将拉您进SKIA中国微信群。
注明WASM爱好者，将拉您进WebAssembly技术交流群。
多年桌面客户端研发经验，希望一起交流、学习。
