Сдвиговые регистры, циклические массивы. Экономим память

Внимание

Для участия в обсуждениях и оформления подписки на новые сообщения форума вам необходимо зарегистрироваться.
Главная » Основные форумы » Обмен опытом
Страницы: 1
RSS
Сдвиговые регистры, циклические массивы. Экономим память
 
#1
23.01.2024 10:03:45
Добрый день,
В этой теме я расскажу кратко что такое сдвиговые регистры и циклические массивы.
И покажу как на Lua  экономить память при создании роботов.
----------------------
При торговле на бирже приходит много информации, такой , как новости, результаты сделок, значения индикаторов, например свечей.
эта информация записывается в массивы и в файлы и может составлять очень большой объем.
------------------
Однако, при реальной торговле, для принятия решения, нет надобности не только во всей накопленной информации в файлах, но и порою нужна лишь информация за последние например 60 минут, свечей с интервалом 1 минута.
=================
Чтобы массивы с данными не разбухали до безумных размеров я реализую временное окно,
в пределах которого  храню текущую информацию.
-------------------
Например, храним только 1024 последних отсчета.
Для этого необходимо выделить массив всего в 1024 элемента.
Для каждого нового отсчета необходимо сдвинуть содержимое массив влево на один отсчет,
а в освободившейся место записать принятое значение.
--------------------
Возникает вопрос как реализовать этот сдвиг элементов массива, чтобы было быстро.
---------------------
Один из приемов - циклические массивы.
-------------------
В таком массиве элементы не двигаются, а двигается указатель на место удаляемого первого элемента .
Это же место является местом размещения принятого элемента.
---------------
Еще одним способом является использование многобитовых регистров процессора, с помощью которых можно реализовать многобитовые сдвиги данных за одну операцию.
===================
В луа есть операции сдвига >>m (<<m).
Они позволяют сдвинуть целое число на m разрядов влево ( вправо), что соответствует делению(умножению) этого числа на 2 в степени m.
Такая операция сдвига числа выполняется в регистре сдвига  ( в процессоре это АЛУ+регистры)
------------------
В современных процессорах Intel есть регистры в 256 бит (в последних 512 бит)
------------------------------
Так как число double занимает 64 бита, а long(integer в lua) 32 бита,
то с помощью этих регистров можно сдвигать не одно число, а массив из 4,8,16 чисел одной командой.
Для простоты будем называть эти регистры 256(512) ,битовыми тоже сдвиговыми регистрами.
------------------
Очевидно, что с помощью этих регистров можно сдвигать массивы чисел.
=======================
Если не использовать С for lua,
то в скрипте на луа можно реализовать два способа работы с такими временными окнами.
------------------------------
Либо циклический массив,
либо сдвиг элементов массива.
--------------------------------------
Так как данный ликбез в основном для начинающих,
то покажу наиболее простой способ, но при этом достаточно быстродействующий.
-------------------------------
Вот скрипт функций, которые реализуют механизм такого временного окна данных,
где N - размер временного окна
Код
local function newCA(N) local t={}; for j=1,N do t[j]=0; end; return t; end --вставка нового элемента
local function setCA(t,X) table.remove(t,1); t[#t+1]=X;  end --вставка нового элемента
Посмотрим, что сохраняется в таком массиве
Организуем цикл записи номеров отсчетов которые изменяются от 1 до M
и какие из отсчетов будут сохраняться в массиве фиксированной длины 32 элемента
Код
local M=1000000
local t=newCA(32)
for j=1,M do setCA(t,j)
print("j="..j..",t="..table.concat(t,","));
end
это содержимое массива на каждом цикле
Код
>D:/lua53/lua53.exe -e "io.stdout:setvbuf 'no'" "test_lines.lua" 
j=1,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
j=2,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2
j=3,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3
j=4,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4
j=5,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5
j=6,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6
j=7,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7
j=8,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8
j=9,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9
j=10,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10
j=11,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11
j=12,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12
j=13,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13
j=14,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14
j=15,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
j=16,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
j=17,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17
j=18,t=0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18
j=19,t=0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19
j=20,t=0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
j=21,t=0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21
j=22,t=0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22
j=23,t=0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23
j=24,t=0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24
j=25,t=0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
j=26,t=0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26
j=27,t=0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27
j=28,t=0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28
j=29,t=0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29
j=30,t=0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
j=31,t=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
j=32,t=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32
j=33,t=2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33
j=34,t=3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34
j=35,t=4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35
j=36,t=5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36
j=37,t=6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37
j=38,t=7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38
j=39,t=8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39
j=40,t=9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40
j=41,t=10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41
j=42,t=11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42
j=43,t=12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43
j=44,t=13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44
j=45,t=14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45
j=46,t=15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46
j=47,t=16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47
j=48,t=17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48
j=49,t=18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49
j=50,t=19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50
j=51,t=20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51
j=52,t=21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52
j=53,t=22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53
j=54,t=23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54
j=55,t=24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55
j=56,t=25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56
j=57,t=26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57
j=58,t=27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58
j=59,t=28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59
j=60,t=29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60
j=61,t=30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61
j=62,t=31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62
j=63,t=32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63
j=64,t=33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64
j=65,t=34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65
j=66,t=35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66
j=67,t=36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67
j=68,t=37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68
j=69,t=38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69
j=70,t=39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70
j=71,t=40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71
j=72,t=41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72
j=73,t=42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73
j=74,t=43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74
j=75,t=44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75
j=76,t=45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76
j=77,t=46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77
j=78,t=47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78
j=79,t=48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79
j=80,t=49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80
j=81,t=50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81
j=82,t=51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82
j=83,t=52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83
j=84,t=53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84
j=85,t=54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85
j=86,t=55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86
j=87,t=56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87
j=88,t=57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88
j=89,t=58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89
j=90,t=59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90
j=91,t=60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91
j=92,t=61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92
j=93,t=62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93
j=94,t=63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94
j=95,t=64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95
j=96,t=65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96
j=97,t=66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97
j=98,t=67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98
j=99,t=68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99
j=100,t=69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100
j=101,t=70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101
j=102,t=71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102
j=103,t=72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103
j=104,t=73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104
j=105,t=74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105
j=106,t=75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106
j=107,t=76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107
j=108,t=77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108
j=109,t=78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109
j=110,t=79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110
j=111,t=80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111
j=112,t=81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112
j=113,t=82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113
j=114,t=83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114
j=115,t=84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115
j=116,t=85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116
j=117,t=86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117
Оценим быстродействие такого метода для массива в 1024 элемента
Код
local M=1000000
local t=newCA(1024)
--nklib.startA();
local tim=os.clock();
for j=1,M do setCA(t,j) end
--local tim=0.1*nklib.stopA()/M
tim=os.clock()-tim
print(1000000.*tim/M.." мкс" )
результат:
Код
>D:/lua53/lua53.exe -e "io.stdout:setvbuf 'no'" "test_lines.lua" 
10.099 мкс
>Exit code: 0
Т .е. на сохранение одного нового элемента в таком массиве затрачивается примерно 10 мкс.
---------------------
Таким образом, с помощью приведенных выше двух простых функций,
Вы можете  управлять расходом оперативной памяти в своем роботе,
исходя из требуемого временного окна обработки поступающих данных.
 
 
#2
23.01.2024 13:41:10
nikolz,  Вы можете сравнить это метод с
local lifo=List.new() List.pushlast(lifo,i) List.popfirst(lifo),
и где какой использовать лучше или предпочтительней?
 
 
#3
23.01.2024 14:06:18
Цитата
VPM написал:
nikolz,  Вы можете сравнить это метод с
local lifo=List.new() List.pushlast(lifo,i) List.popfirst(lifo),
и где какой использовать лучше или предпочтительней
Я уже сравнивал и вам в вашей теме выложил результат.
Вы очевидно его не читали.
------------
Если кратко, то Ваш вариант ничего не экономит.
Вы посмотрите там результат работы сборщика и пояснение почему Вы заблуждаетесь с этим вариантом.
--------------------
Если будет непонятно, то поясню дополнительно.
 
 
#4
23.01.2024 14:55:51
Я Вам говорю про этот вариант, в Вашем первоначальном есть логическая ошибка, это тоже окно ну или стек:

Пример от nikolz,  оказал не оценимую помощь, помог разобраться в чем была путаница и не до понимание, помог собрать вариант который я объяснял.

Ниже пример, то о чем пытался я сказать.
И что мы видим, реализован принцип LIFO  «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это вариант стека с помощью двусторонней очереди, не смотря на то что алгоритм называется двусторонняя очередь, собран СТЕК!  

function List.new()
 --return {first = 0, last = -1}
 return {first = 0, last = 0}
end

Код
local list=List.new()
local length=10; local M=1000--00--00
print("объем начального массива", M, "Кол. элементов в созданном length=",length);
local count1 = collectgarbage("count") -- получаем текущий размер памяти
------------------------------ LIFO
for i=1, M do

print(i, ')','Начальные индексы', 'list.first =', list.first, '; list.last =', list.last )

List.pushlast(list,i)
print(i, ')','Вставил', 'index list.last =', list.last,'; присвоил значение элементa =',list[list.last], '(',collectgarbage("count"),')' )

if i>length then
List.popfirst(list)
print( i, 'Операция - Удаление первого:', ')', 'присвоил индекс первоve элементу =', list.first, 'вернул значение первого элементa =', list[list.first] ,'(',collectgarbage("count"),')' ) --, list.first
end

end
print("LIFO (вариант реализации стека с помощью двусторонней очереди.) ----------------------");
print("начальный объем занятой памяти",count1);

print("число элементов в LIFO list после "..(M).." циклов функции рор=" ..(list.last-list.first))
local countOUT = collectgarbage("count")
print("объем занятой памяти",countOUT);
--------------------------------
collectgarbage("collect")
print("объем занятой памяти после сборщика мусора",collectgarbage("count"));
 
 
#5
23.01.2024 17:11:21
Цитата
VPM,
Возможно я не понял, вопроса,
Но так как Вы возвращаетесь к этой идеи уже многократно, то поясню подробнее в чем у Вас ошибка.
---------------------
Во-первых, в терминологии.  
Вы уж не обижайтесь, но прежде, чем обсуждать надо быть уверенным ,
что мы с вами горшками называем горшки, а цветами -цветы.
------------------
Так вот,
Стек и очередь это две большие разницы.
Стек - это кипа - т е представьте кипу листов бумаги на столе. Вы положили лист сверху и взяли его.
--------------------
или еще пример стека - это обойма в автомате  патрон лежащий сверху выйдет первым.
-----------------
Т е принцип последним зашел -первым вышел.
-------------------------
Очередь  -это первый зашел и первым купил.
Наглядный пример - очередь в магазине за яйцами.
------------------------
Поэтому невозможно стек сделать из очереди.
Если конечно Вы не сторонник смотреть гланды через зад.
====================
Но это не главное.
========================
Давайте посмотрим на то как вы пытаетесь  уменьшить память, создав нечто,
в котором Вы синхронно выкидываете первый элемент и запихиваете последний.
----------------------------
Ничего это вам не напоминает? А посмотрите эту мою тему Про сдвиговые регистры.
Именно это и происходи в них.
--------------------
Но они реализуются методами, которые я описал выше.
===================
Если же Вы будете просто в массиве луа стирать первый элемент,
записывая туда nil и добавлять в конец новый, то массив будет увеличиваться на этот новый элемент.
----------------------------------------
В луа для хранения одного числа в таблице тратится 12 байт.
Когда Вы пишите nil в первый элемент, то память из под него не освобождается,
так как ее невозможно удалить из того блока памяти, который уже выделен для этого массива.  
-------------------
В лучшем случае освободится память на элемент массива, если он является тоже таблицей.
======================
вот ваш вариант.
Код
---- Операции вставки -- table.insert
function List.pushlast (list, value)   local last = list.last + 1;   list.last = last;   list[last] = value; end
---- Операции удаления -- table.remove
function List.popfirst (list)
  local first = list.first;  if first > list.last then   return nil   end
  local value = list[first]   list[first] = nil   list.first = first + 1  return value  end
list[last] = value;  -- этот оператор записывает в таблицу новое значение.
--------------------------------
При создании таблицы , ей выделяется место в оперативной памяти.  
----------------------------------
Если при записи нового значения места не хватает, то оно будет увеличено.
-----------------------
C точки зрения сборки мусора.
Объектом для сборки является вся таблица, а не отдельная ее ячейка.
================
Когда Вы в функции popfirst  делаете это:    list[first] = nil
то в ячейке таблицы в параметр тип элемента записывается ноль.
Но память для хранения этого типа и значения элемента не может быть освобождена,
так как она не является самостоятельным объектом. Это часть память таблицы.
=======================
Таким образом, в вашем варианте таблица может только увеличивать объем занимаемой памяти, но не уменьшать ее.
=========================
Уменьшать, можно лишь так, как я рассказал в этой теме.
 
 
#6
23.01.2024 17:25:07
и еще...
ваша стек-очередь напоминает недоделанный циклический массив.
Если его доделать, то он будет делать ровно тоже самое, что и мой вариант сдвига массива выше.
--------------------
Циклический массив работает быстрее, чем сдвиг массива.
Но в луа из него медленнее брать данные.
Его интереснее делать на C и встраивать сразу в индикаторы и фильтры.
Но это уже другая тема.
 
 
#7
23.01.2024 17:50:31
nikolz,  Вы попробуйте пример,   никакие nil не вставляются, если Вы об этом
if first > list.last then   return nil   end,
то это только проверка на ошибку.

В моем примере этой ошибки быть не может, так как вставляется последний элемент,  массив нарастает до значения length  if i>length then, (то есть определен размер окна).
После достижения идет присвоение последнего  и переписывание первого значения окна. Все.
 
 
#8
23.01.2024 17:57:42
Вот из букваря:

Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO).
Это значит, что мы будем иметь доступ только к последнему добавленному элементу.

Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов.
Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO).
То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.

Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди.
В дек можно добавлять или удалять элементы как с начала, так и с конца очереди.
Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных.

Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.
 
 
#9
23.01.2024 18:17:11
nikolz,  Это я и хотел сравнить, сделать один размер массивов, один размер окна прогнать на скорость на память, на время исполнения?
Цитата
nikolz написал:
и еще...
ваша стек-очередь напоминает недоделанный циклический массив.
Если его доделать, то он будет делать ровно тоже самое, что и мой вариант сдвига массива выше.
--------------------
Циклический массив работает быстрее, чем сдвиг массива.
Но в луа из него медленнее брать данные.
Его интереснее делать на C и встраивать сразу в индикаторы и фильтры.
Но это уже другая тема.
 
 
#10
24.01.2024 07:58:14
Цитата
VPM написал:
nikolz,  Это я и хотел сравнить, сделать один размер массивов, один размер окна прогнать на скорость на память, на время исполнения?
Цитата
nikolz написал:
и еще...
ваша стек-очередь напоминает недоделанный циклический массив.
Если его доделать, то он будет делать ровно тоже самое, что и мой вариант сдвига массива выше.
--------------------
Циклический массив работает быстрее, чем сдвиг массива.
Но в луа из него медленнее брать данные.
Его интереснее делать на C и встраивать сразу в индикаторы и фильтры.
Но это уже другая тема.
Вы нем поняли. В вашем случае нельзя сделать размер постоянным.
Он будет лишь увеличиваться при записи в конец.  Но не будет уменьшаться.
----------------
Это я показал Вам в своем тесте.
Там в конце Ваша очередь-стек имеет ноль элементов , но размер памяти занятый массивом остался такой же как при записи миллиона элементов.
--------------------
В моем варианте Вы изначально фиксируете длину массива и она остается всегда такой же.
 
 
#11
24.01.2024 08:00:51
Цитата
VPM написал:
Вот из букваря:

 Стек   — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO).
Это значит, что мы будем иметь доступ только к последнему добавленному элементу.

 Очереди     очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов.
Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO).
То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.

 Двусторонняя очередь   (Double-ended queue), или дек (Deque), расширяет поведение очереди.
В дек можно добавлять или удалять элементы как с начала, так и с конца очереди.
Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных.

Позже мы рассмотрим   вариант реализации стека с помощью двусторонней очереди  .
Будем считать, что у нас разные определения этих понятий.
------------------------------
Но это не важно.
Важно, что ваш вариант не работает.
 
 
#12
24.01.2024 08:02:49
Если Вы считаете, то просто покажите свой тест и результаты и будет предмет обсуждения.
Пока же у Вас лишь программа и ваша вера, что она экономит память.
 
 
#13
24.01.2024 08:03:27
Если Вы считаете, что Вы правы, то просто покажите свой тест и результаты и будет предмет обсуждения.
Пока же у Вас лишь программа и ваша вера, что она экономит память.
 
 
#14
24.01.2024 08:36:11
nikolz,  программа и тест есть на 25 странице в моей теме Двойные очереди.

Сложно с Вами с программистами, каждый на своей волне, "забейте", проще самому провести.
 
 
#15
24.01.2024 08:43:49
VPM,
вот результаты  тестов:
это тест моих функций  сдвиговый  массив.
Код
local M=1000000
local t=newCA(1024)
for i=1, M do  setCA(t,i) end
count1 = collectgarbage("count") print("объем занятой памяти",count1//1);
--------------------------------
collectgarbage("collect") count1 = collectgarbage("count") print("объем занятой памяти после сборщика мусора",count1//1);
результат:
Код
>D:/lua53/lua53.exe -e "io.stdout:setvbuf 'no'" "Test_List.lua" 
объем занятой памяти   82.0
объем занятой памяти после сборщика мусора   76.0
>Exit code: 0
тест циклический массив:
Код
local M=10000000
local t=nk_newV(1024)
for i=1, M do  nk_push(t,i) end
count1 = collectgarbage("count") print("объем занятой памяти",count1//1);
collectgarbage("collect") count1 = collectgarbage("count") print("объем занятой памяти после сборщика мусора",count1//1);
результат:
Код
>D:/lua53/lua53.exe -e "io.stdout:setvbuf 'no'" "Test_List.lua" 
объем занятой памяти   97.0
объем занятой памяти после сборщика мусора   91.0
>Exit code: 0
тест для Вашей функции
Код
local M=10000000
local list=List.new()
local count1 = collectgarbage("count") print("начальный объем занятой памяти",count1//1);
--------------------------
for i=1, M do  List.pushlast(list,i)   end
collectgarbage("collect") count1 = collectgarbage("count")  print("объем занятой памяти после сборщика мусора",count1//1);
результат:
Код
>D:/lua53/lua53.exe -e "io.stdout:setvbuf 'no'" "Test_List.lua" 
начальный объем занятой памяти   65.0
объем занятой памяти после сборщика мусора   262203.0
>Exit code: 0
Какой еще тест сделать?
 
 
#16
24.01.2024 09:00:14
VPM,
Можете пояснить,
как в вашем варианте прочитать весь массив с 1 по последний
и сколько времени на это уйдет по сравнению с чтением типа t[i]  где i от 1 до #t.
--------------
И для какой задачи Вы планируете его применять.
-------------
Я определил область применения моего варианта.
А как применять Вашу очередь?
 
 
#17
24.01.2024 09:04:09
VPM,
Я ранее написал, что Ваш вариант - это недоделанный циклический массив, тест которого я привел вторым.
Рекомендую доделать, тогда будет работать , но чтение из него в луа, как тоже уже писал, медленнее чем из сдвигового.
 
 
#18
24.01.2024 09:06:53
чтобы массив был ограничен по размеру, его надо закольцевать.
Очевидно, Виктор  это не проходил.  
 
 
#19
24.01.2024 10:47:29
nikolz, Не знаю кто что проходил, но мой вариант  Вот ,
Код
function List.new()
 --return {first = 0, last = -1}
 return {first = 0, last = 0}
end

local list=List.new()
local length=10; local M=1000--00--00
print("объем начального массива", M, "Кол. элементов в созданном length=",length);
local count1 = collectgarbage("count") -- получаем текущий размер памяти
------------------------------ LIFO
for i=1, M do

print(i, ')','Начальные индексы', 'list.first =', list.first, '; list.last =', list.last )

List.pushlast(list,i)
print(i, ')','Вставил', 'index list.last =', list.last,'; присвоил значение элементa =',list[list.last], '(',collectgarbage("count"),')' )

if i>length then
List.popfirst(list)
print( i, 'Операция - Удаление первого:', ')', 'присвоил индекс первоve элементу =', list.first, 'вернул значение первого элементa =', list[list.first] ,'(',collectgarbage("count"),')' ) --, list.first
end

end
print("LIFO (вариант реализации стека с помощью двусторонней очереди.) ----------------------");
print("начальный объем занятой памяти",count1);

print("число элементов в LIFO list после "..(M).." циклов функции рор=" ..(list.last-list.first))
local countOUT = collectgarbage("count")
print("объем занятой памяти",countOUT);
--------------------------------
collectgarbage("collect")
print("объем занятой памяти после сборщика мусора",collectgarbage("count"));
это стек, который в трейдинге называют динамическим окном, у меня в этом примере все доделано,  
то что вы демонстрируете это просто вставка элементов в массив, как она вообще может уменьшаться?
 
 
Страницы: 1
Читают тему
Техническая поддержка
+7 383 219 1606
© 2000–2024,
ARQA Technologies
Наверх