Уменьшите размер массива целых чисел следующим образом: «[12, 1, -34, 55, 13, 341, 11, 56, 321, -3422, 1222, -4, 237]», сохраняя при этом возможность преобразовать его обратно. в исходное состояние. Сжатый вывод должен быть строкой.
Из-за слишком длинных строк менеджер баз данных, который я использую, зависает при взаимодействии с ним. (Строки используются в качестве формата хранения для типов переменных, таких как массивы.)
По сути, я храню список координат сетки следующим образом: [Vector3(1,2,3), Vector3(4,5,6)] -> [1,2,3,4,5,6]
Я строю это в gdscript.
Моя лучшая попытка собрать воедино числа из первого примера целочисленного массива привела к следующему:
"c1-y.Td,y1.bU,w1-ym,cm-4,n7"
Путем присвоения связанных чисел > 9 нечисловому символу (например, 10 = a, 11 = b, 61 = Z) и размещать запятые только между преобразованными числами, состоящими из нескольких символов (а также использовать символ «-» в качестве своего рода запятой (это несколько сложно)). Это уменьшение размера в среднем на 48% без учета пробелов (проверено 200 случайно сгенерированных массивов).
Есть ли лучший способ сделать то, что я пытаюсь сделать?
Вот мое решение в gdscript, если оно кому-то понадобится.
extends Node
var negative_character_index = 50000
#skip all white space characters as well as "." and "," and "()"
#these are used for special cases
var start_char = 47
func num_to_char(num: int):
var x = abs(num)
if x > negative_character_index:
#too large
return
else:
x += start_char
if num < 0:
x += negative_character_index
var char = String.chr(x)
return char
func char_to_num(char : String):
var x = char.unicode_at(0) - start_char
if x == null:
#maybe negative_character_index was changed
breakpoint
if x > negative_character_index:
x -= negative_character_index
x *= -1
return x
#shorten int
func int_to_compact_int_string(n:int):
var compact_n = ""
#largest convertable number
var head = ""
var last_head_int = null
var last_char = null
var get_zeros_code = func(head):
var zeros = 0
if head.begins_with("0"):
for char2 in head:
if char2 == "0":
zeros += 1
else:
break
if head.right(1) == "0":
zeros -=1
if zeros > 0:
return "("+str(zeros)+")"
return ""
for num in str(n):
head += num
print(head)
if num != "-":
var head_int = str_to_var(head)
var char = get_zeros_code.call(head) + num_to_char(head_int)
print(char)
if last_head_int != null && char == null:
compact_n += last_char
head = ""
head += num
last_head_int = str_to_var(head)
last_char = get_zeros_code.call(head) + num_to_char(last_head_int)
else:
last_head_int = head_int
last_char = char
print("~~~")
if head != "":
print(head)
print(last_char)
print("~~~")
compact_n += last_char
return compact_n
func int_arr_to_compact_str(int_arr):
var compact_str = ""
var is_multi = false
for n in int_arr:
var compact_n:String = int_to_compact_int_string(n)
if compact_n.length() > 1: #seperate multicharacter compact numbers
compact_str += ","
is_multi = true
elif is_multi:
compact_str += "."
is_multi =false
compact_str += compact_n
return compact_str
func new_compact_int_string_to_int(compact_n:String):
var n = ""
var is_zeros = false
var zeros = ""
for char in compact_n:
if char == "(":
is_zeros = true
zeros = ""
elif char == ")":
is_zeros = false
var i = 0
while i < str_to_var(zeros):
n += "0"
i+=1
elif is_zeros:
zeros += char
else:
var index = char_to_num(char)
if index > negative_character_index:
index -= negative_character_index
index *= -1
n += str(index)
return str_to_var(n)
func new_compact_str_to_int_arr(compact_str):
var int_arr = []
var is_multi = false
var multi_compiler = ""
for char in compact_str:
if char == ',' || char == '.':
is_multi = char == ','
#end compiler
if multi_compiler.length() >0:
int_arr.append(new_compact_int_string_to_int(multi_compiler))
multi_compiler = ""
else:
if is_multi:
multi_compiler += char
else:
int_arr.append(new_compact_int_string_to_int(char))
if multi_compiler.length() > 0:
int_arr.append(new_compact_int_string_to_int(multi_compiler))
multi_compiler = ""
return int_arr
func _ready():
var arr2 = [237, 50001, -5000000003, 250000000]
#print("---")
#for i in range(999):
#print(String.chr(i)+" -> "+str(i))
#print("---")
print(arr2)
var comp = int_arr_to_compact_str(arr2)
print(comp)
var r_arr2 = new_compact_str_to_int_arr(comp)
print(r_arr2)
Каков диапазон целых чисел?
Вы можете преобразовать в коды UTF-16 (0–65535) со знаком:
const arr = [12, 1, -34, 55, 13, 341, 11, 56, 321, -3422, 1222, -4, 237];
const result = arr.map(n => (Math.sign(n) < 0 ? '-' : '') + String.fromCharCode(Math.abs(n))).join('');
console.info(result);
console.info(arr.join(',').length, '=>', result.length);
//decode
const out = [];
for(let i=0;i<result.length;i++){
const sign = result[i]==='-'?-1:1;
if (sign<0) i++;
out.push(result[i].charCodeAt()*sign);
}
console.info(...out);
Вы можете использовать первый бит для хранения знака, хотя диапазон сужается до максимума 32768:
const arr = [12, 1, -34, 55, 13, 341, 11, 56, 321, -3422, 1222, -4, 237];
const result = arr.map(n => {
let c = Math.abs(n);
c = (c << 1) + (Math.sign(n) < 0 ? 1 : 0);
return String.fromCharCode(c);
}).join('');
console.info(result);
console.info(arr.join(',').length, '=>', result.length);
//decode
const out = [];
for(let i=0;i<result.length;i++){
const n = result[i].charCodeAt();
out.push((n >> 1) * (n & 1 === 1 ? -1 : 1));
}
console.info(...out);
Начну с того, что кодировка, которую вы придумали, неплохая. Однако есть немного возможностей для улучшения.
Чтобы получить «идеальную» кодировку, вам нужно сделать всего 3 вещи:
Все это звучит не так уж сложно, но на самом деле шаг 3 — это вся работа по сжатию данных без потерь. Это было бы легко, если бы не фраза «одинаково вероятно» двусмысленная. Он предполагает статистическую модель входных данных, и чем лучше эта модель, тем большее сжатие вы можете получить. Эти модели могут быть довольно сложными.
Поскольку это действительно так сложно, если вас это действительно волнует, вам обычно следует использовать надежный компрессор, например:
Однако если вас это не особо волнует, то вот простая схема, которая оптимальна для распространенных распределений целых чисел, симметричных относительно 0. Допустим, ваш набор символов состоит из M символов, которые мы будем называть «цифрами». «от 0 до М-1. Чтобы закодировать целое число:
// encode integer to string with M digits
encodeInt(int n) -> string:
// exactly one representation for 0
if (n === 0):
return digits[0];
// range of remaining digits
rangestart = 1
rangeend = M
if (n > 0):
// N is positive. move first possibility to 0
n-=1
// use lower half of range
rangeend = ceil((rangeend + rangestart)/2)
else:
// N is negative. Flip sign move first possibility to 0
n = -n - 1
// use upper half of range
rangestart = ceil((rangestart + rangeend)/2)
T = thresholds[0]
if (n < T):
// n is small, encode in one character
return digits[rangestart+n];
//n is big
//remove small encodings from range
rangestart += T
range = rangeend-rangestart
//Encode n%range in the first digit, and the rest in next digits
return digits[n%range] + encodePos(floor(n/range), 1) // + is string concatenation
// encode positive integer to string with M digits
encodePos(int n, int place) -> string:
T = thresholds[place]
if (n < T):
// n is small, encode in one character
return digits[n];
// n is big
range = M - T
return digits[n%range] + encodePos(floor(n/range), place+1)
Обратите внимание, что есть параметры, которые я не указал — массив thresholds
.
Чтобы получить «оптимальную» кодировку, эти пороги следует выбирать так, чтобы вероятность увидеть n
>= или < порога была пропорциональна количеству символов, доступных выше или ниже порога.
Эта кодировка является саморазграничивающейся, поэтому для кодирования всего массива просто закодируйте все числа и объедините их вместе. ,
или другой разделитель не нужен.
Это похоже на проблему XY - если у вас нет миллионов таких коллекций, можете ли вы подготовить сопоставление с какой-то новой справочной таблицей и получить их из другой таблицы?
Вам нужно будет подумать, как они будут отображаться обратно, но, возможно, вы сможете получить более хорошее решение, возможно, сериализовав каждый отдельный Vector
(или просто его элементы) вместо N элементов векторов в отдельные поля или N неупакованных векторов, добавив NULL
поля. для отслеживания различной длины и т. д.
Это также хорошее решение. хотя я бы предпочел, чтобы все мои данные для этого были в одной таблице, если зубрежка работает достаточно хорошо. Меньше накладных расходов (с точки зрения отсутствия необходимости извлекать данные из более чем одной таблицы) мне кажется лучше.
У меня нет возможности протестировать ваш конкретный сценарий, но в этом действительно преимущество нескольких таблиц; скромный SELECT * FROM _ JOIN _ ON _ WHERE _
удивительно быстр и должен привести к сопоставимому общему объему передачи данных.. хотя учтите, что вы можете получить дополнительное замедление и выгоду от дизайна, в котором у вас есть несколько таблиц целых чисел с разной длиной столбцов для учета очень разных длин векторной распаковки
the most compact way to cram a list of integers into a string
такие, чтобы их можно было получить/восстановить.