On 03/06/14 17:10, Roger Hui wrote:
Probably not. It's not related to the problem of finding the minimum that
I know of. It's the general problem of how you avoid initializing a large
but sparse array. Recently, I did use the idea in a case of x i. y (you
know, the problem I've been working on for 30 years :-).
Anyway, here it is: In the book *The Design and Analysis of Computer
Algorithms*, by Aho, Hopcroft, and Ullman, Addison-Wesley, 1974, Exercise
2.12:
Develop a technique to initialize an entry of a matrix to zero the first
time it is accessed, thereby eliminating the O(‖V‖^2) time to initialize an
adjacency matrix.
[Hint: Maintain a pointer to each initialized entry to a back pointer on a
s/Maintain a pointer *to* each initialized entry/Maintain a pointer *in* each
initialized entry/
he says after taking to book off his shelf and opening it to Exercise 2.12.
Thanks for the reminder about that idea.
The point is that you control the small dense table of back-pointers to
initialized data in the otherwise uninitialized large array. Checking if an
entry in the large sparse array holds initialized data reads a pointer (or
index) from the large array, uses that to find if there's a back-pointer (or
index) in the small dense array that refers to that entry. The data for an
entry is in (or parallel to) the small dense array. You do need more space to
hold the pointers and back-pointers, but only one pointer/back-pointer pair per
initialized entry. If you treat the small dense array as a stack (e.g., with a
top-of-stack marker) then you don't have to initialize the memory for the small
dense array either.
... peter
stack. Each time an entry is accessed, verify that the contents are not
random by making sure the pointer in that entry points to the active region
on the stack and that the back pointer points to the entry.]
The hint is part of the statement of the exercise in the book and gives
away the game. The technique is sufficiently well-known that it is the top
search result (of 3,800,000) on Googling "Exercise 2.12
sparse"<http://www.google.ca/search?q=Exercise+2.12+sparse>
.
On Thu, Mar 6, 2014 at 4:55 PM, Raul Miller <rauldmil...@gmail.com> wrote:
Is this still going to be faster than the test and branch loop?
Thanks,
--
Raul
On Thu, Mar 6, 2014 at 7:49 PM, Roger Hui <rogerhui.can...@gmail.com>
wrote:
Well, if you use a hash table it'd be O(1) expected time to read and
write.
The method I know is O(1) worst case time to read and write.
On Thu, Mar 6, 2014 at 2:54 PM, Yike Lu <yikelu.h...@gmail.com> wrote:
Hmm, maybe not. It has to basically be able to insert ordered in
constant
time. Everything I remember seems to be log time for one or the other.
I'm starting to lean towards a multi-pass / multi-array solution.
On Thu, Mar 6, 2014 at 4:42 PM, Roger Hui <rogerhui.can...@gmail.com>
wrote:
The method I know offers O(1) time to read and write. Can your
dictionary
do the same? (And I think we are talking about _how_ you implement a
dictionary.)
On Thu, Mar 6, 2014 at 2:34 PM, Yike Lu <yikelu.h...@gmail.com>
wrote:
Using a dictionary is another way.
On Thu, Mar 6, 2014 at 3:30 PM, Roger Hui <
rogerhui.can...@gmail.com>
wrote:
Yes, that's the cost. The trick is to avoid initializing count
altogether,
because for this subproblem M is much greater than n. The answer
is
algorithmic and not a matter of using this or that C operation.
Recently I had occasion to use the trick for M=65536 and n about
5000.
As
originally posed, I think the intention was that M would be
zillions.
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
