Tiny fractal studio :-)

[0x69]

You should try to get it to calculate and draw a maximum number of lines per frame so there's no lag and the detail can be as large as you want. Rather than doing all operations in a single "frame" which gets exponentially more computationally intensive, maybe you could just run through a set number of lines in each frame. That way the fractal would slowly draw itself and the program wouldn't hang.

Would that work?

Ehm, in principle that is possible. But ... there is 2 "buts" :

1. Lets say fractal is drawn from some table fractal = {x1,y1,x2,y2,x3,y3,...}. After calculating next fractal stage - fractal table is erased and re-inserted all new fractal points (Now it is like that). To be able to do like you say, we should change that table dynamically, -> remove some points then add some points. This means that there will be needed :
- length_of_fractal_table number of deletes from fractal table
- inserts into fractal table must be performed not at the end of table, but everywhere (in start of table, somewhere in between of table, etc.)
These two things I suppose will extend total time needed for fractal calculation. (Requirement of deletes - certainly will extend computations. What about inserts not in the end of table - i don`t know, it may extend computation time also,- but generally will depend on How tables are implemented in Lua. This answer possibly knows Roberto Ierusalimschy, or we should check Lua core description or research Lua C++ source )

2. Lets just pretend that everyhing went fine - your proposal will just let us see *intermediate* calculation steps, but total time of fractal computation will not decrease. I think this is crucial. What user will do with unfinished intermediate fractal ? I mean that implementation of such thing will not give us any striking advantage. (Striking advantage would be if we manage to shorten total computation time, or lets say somehow add color effects on fractal


Good luck!

[Robin]

1. Lets say fractal is drawn from some table fractal = {x1,y1,x2,y2,x3,y3,...}. After calculating next fractal stage - fractal table is erased and re-inserted all new fractal points (Now it is like that). To be able to do like you say, we should change that table dynamically, -> remove some points then add some points. This means that there will be needed :
- length_of_fractal_table number of deletes from fractal table
- inserts into fractal table must be performed not at the end of table, but everywhere (in start of table, somewhere in between of table, etc.)

Is it even necessary to remove points? All points at generation n still exist in generation n+1, right?

2. Lets just pretend that everyhing went fine - your proposal will just let us see *intermediate* calculation steps, but total time of fractal computation will not decrease. I think this is crucial. What user will do with unfinished intermediate fractal ? I mean that implementation of such thing will not give us any striking advantage. (Striking advantage would be if we manage to shorten total computation time, or lets say somehow add color effects on fractal

There is one definite advantage to showing intermediate steps: for people, perceived time is more important than real time, and showing something in between will help to decrease the first.

[0x69]

Is it even necessary to remove points? All points at generation n still exist in generation n+1, right?

Yep, I made a mistake,- removes isn`t needed in principle. But still there exist potential perfomance problem of insertion not in the end of table

There is one definite advantage to showing intermediate steps: for people, perceived time is more important than real time, and showing something in between will help to decrease the first.

You may be right, but now I don`t have any wish to implement *nice switch between fractal stages*. I better focus on my new projects

[Robin]

You may be right, but now I don`t have any wish to implement *nice switch between fractal stages*. I better focus on my new projects

Good. It would be a shame if you wouldn't do anything new.

[0x69]

You may be right, but now I don`t have any wish to implement *nice switch between fractal stages*. I better focus on my new projects

Good. It would be a shame if you wouldn't do anything new.

Thanks

BTW, I made a quick test about perfomance issues regarding insertion into somewhere in between of table.
Test code:

Code: Select all

local times=80000
function InsertInTheEnd()
	local t={}
	for i=1,times do
		table.insert(t,1)
	end
end
function InsertInBetween()
	local t={}
	for i=1,times do
		table.insert(t,math.random(1+#t),1)
	end
end
t1=os.clock()
	InsertInTheEnd()
t2=os.clock()
	InsertInBetween()
t3=os.clock()
print("Insertion of "..times.." elements:\n",
	t2-t1.." sec. => In the end of table\n",
	t3-t2.." sec. => Somewhere in between of table",
	"\nSlowDown is => "..math.floor((t3-t2)/(t2-t1)).."x")

Results:

Insertion of 80000 elements:
0.031 sec. => In the end of table
29.344 sec. => Somewhere in between of table
SlowDown is => 946x

I don`t want that generation of fractal will slowdown by such a huge number of times!! only because of addition of drawing of intermediate steps...
(It can be that this slowdown number is not accurate, but you get the point what "dynamic" insertion into table does to perfomance)

[Robin]

Code: Select all

function InsertInTheEnd()
	local t={}
	for i=1,times do
		table.insert(t,1)
	end
end
function InsertInBetween()
	local t={}
	for i=1,times do
		table.insert(t,math.random(1+#t),1)
	end
end

This isn't completely fair, since the second one has to

1. Get global "math".
2. Get field "random".
3. Get length of t.
4. Add it to 1.
5. Call a field.

Maybe this would give fairer results:

Code: Select all

function InsertInTheEnd()
	local t={}
	for i=1,times do
		math.random(1+#t)
		table.insert(t,1)
	end
end
function InsertInBetween()
	local t={}
	for i=1,times do
		table.insert(t,math.random(1+#t),1)
	end
end

[bartbes]

I agree with Robin.

[0x69]

Maybe this would give fairer results:

Code: Select all

function InsertInTheEnd()
	local t={}
	for i=1,times do
		math.random(1+#t)
		table.insert(t,1)
	end
end
function InsertInBetween()
	local t={}
	for i=1,times do
		table.insert(t,math.random(1+#t),1)
	end
end

Still SlowDown is => 957x. So what conclusion we can make ? Maybe that "math.random(1+#t)" has nothing to do with essential reason of slowdown ? Right ?

Lets face it - I`ve accepted my reasoning mistake about "needed deletes from table",- now you accept the fact what is going on with slowdown. This will be fair, Right ? (Otherwise you will only show to others that you only like to point argument errors of opponents, but you didn`t accept yours argument mistakes. Such people are really very unfair).

Good luck !

[bmelts]

Hey, relax. No one's refusing to accept your argument. Robin just wanted to make sure to remove all outside influences from the results, to ensure that they're completely legitimate. Otherwise, they could be skewed by some irrelevant factor and undermine your hypothesis. I think that's reasonable to do.

That said, these results shouldn't really come as a surprise. Inserting something at the end of an array is easy and fast (constant time), while inserting something in the middle means shifting everything afterward forward in memory, which is comparatively slow (linear time). It's not a big deal for small tables or if you only do it occasionally, but doing it every iteration of a loop for tables more than a few thousand keys large is going to demonstrate some noticeable slowdown.

As for how Lua implements tables, they're implemented as a hybrid data structure: there's a hash table part, which stores key-value pairs (this was the entirety of the table implementation prior to 5.0), and an array part, which acts like a standard array, storing values in contiguous memory with implicit keys. The array part is more efficient to use than the hash table part in general, though keep in mind that the array part can only store values with integral keys that are continuous from 1 to some other number. Here's an example showing how a table can serve double-duty:

Code: Select all

t = {}
t[1] = "foo" -- stored in the array part
t[2] = 0 -- stored in the array part
t[100] = 42 -- stored in the hash table part - it's not continuous (there's a gap from 3-99) and thus can't be part of the array
t["love"] = math.rad -- stored in the hash table part

For more information on the internals of Lua, check out this PDF.

[Robin]

Hey, relax. No one's refusing to accept your argument. Robin just wanted to make sure to remove all outside influences from the results, to ensure that they're completely legitimate. Otherwise, they could be skewed by some irrelevant factor and undermine your hypothesis. I think that's reasonable to do.

Exactly. I just wanted to make sure the science was right.

You were right, 0x69.