Время от времени появляется задача вида "сколько мб/c проходит через эту функцию"
Вот, попросил chat gpt сделать замену для redis ts.add и ts.range
В начале он предложил обычный массив, я попросил его переделать на ring buffer
Потом попросил добавить очистку c логарифмической сложностью, он мне выдал avl дерево
Далее, попросил вместо дерева вернуть ring buffer и добавить binary search.
На всё ушло 5-10 минут.
Ниже результат, моих исправлений — я только упростил логирование.
Сам для интересу сделал такую же задачу, с покрытием тестами. У меня на всё, включая отладку до 16 часов. Реализация правда посложнее, я сделал три реализации буфера — обычный на массиве, кольцевой и деку, плюс кое какие дополнительные минорные вещи и упаковку всего в пакет для npm + настройка билдов.
Подозреваю, еще год-два, и подобные задачи можно будет полностью делегировать ai. Программирование рано или поздно станет как арифметика — все пользуются калькулятором, и двузначные числа в уме мало кто умеет складывать.
class RingBuffer {
size: number;
buffer: any[];
start: number;
end: number;
count: number;
constructor(size: number) {
this.size = size;
this.buffer = new Array(size);
this.start = 0;
this.end = 0;
this.count = 0;
}
isFull() {
return this.count === this.size;
}
isEmpty() {
return this.count === 0;
}
add(element: any) {
this.buffer[this.end] = element;
this.end = (this.end + 1) % this.size;
if (this.isFull()) {
this.start = (this.start + 1) % this.size;
} else {
this.count++;
}
}
getElements() { // <-- неэффективно, проще выставить reduce,
const elements = [];
for (let i = 0; i < this.count; i++) {
elements.push(this.buffer[(this.start + i) % this.size]);
}
return elements;
}
removeOldElements(cutoffTimestamp: number) {
const elements = this.getElements();
const index = RingBuffer.binarySearch(elements, cutoffTimestamp);
if (index < elements.length) {
// Update start and count based on the binary search result
const numElementsToRemove = index;
this.start = (this.start + numElementsToRemove) % this.size;
this.count -= numElementsToRemove;
}
}
static binarySearch(elements: any[], cutoffTimestamp: number) {
let low = 0;
let high = elements.length - 1; // <-- ошибка, т.к. это ring buffer, так работать не будет
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (elements[mid].timestamp < cutoffTimestamp) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low; // Low will be the index of the first element >= cutoffTimestamp
}
}
class TimeSeries {
retentionPeriod: number;
dataBuffer: RingBuffer;
constructor(retentionPeriod: number, bufferSize: number) {
this.retentionPeriod = retentionPeriod; // Retention period in milliseconds
this.dataBuffer = new RingBuffer(bufferSize);
}
addMeasurement(value: number | string) {
const timestamp = Date.now();
this.dataBuffer.add({ timestamp, value });
this.cleanup();
}
getRecentMeasurements() {
const now = Date.now();
const cutoffTimestamp = now - this.retentionPeriod;
// Perform cleanup before fetching recent measurements
this.cleanup();
const recentMeasurements = [];
const elements = this.dataBuffer.getElements();
for (const element of elements) {
if (element.timestamp >= cutoffTimestamp) {
recentMeasurements.push(element.value);
}
}
return recentMeasurements;
}
cleanup() {
const now = Date.now();
const cutoffTimestamp = now - this.retentionPeriod;
// Remove old elements using binary search
this.dataBuffer.removeOldElements(cutoffTimestamp);
}
}
// Example usage
const retentionPeriod = 10000; // 10 seconds
const bufferSize = 100; // Size of the ring buffer
const timeSeries = new TimeSeries(retentionPeriod, bufferSize);
let x = 0;
let y = 0;
// Add some measurements
setInterval(() => timeSeries.addMeasurement('x' + (x += 31)), 2000); // Wait for 2 seconds
setInterval(() => timeSeries.addMeasurement('y' + (y += 11)), 3000); // Wait for another 2 seconds
// Get recent measurements after some delay
setInterval(() => {
const series = timeSeries.getRecentMeasurements();
console.log('Recent measurements:', series);
}, 6000); // Wait for another 2 seconds