[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Will guile support R7RS terminating "equal?" in the presence of cycl
From: |
Stefan Israelsson Tampe |
Subject: |
Re: Will guile support R7RS terminating "equal?" in the presence of cycle? |
Date: |
Mon, 3 Sep 2012 15:55:19 +0200 |
No
I wanted to say that you create a linearisation of the search and apply tourtouse hare on that. One can make that linearisation fast for list traversals but expensive for deep trees. To note here is that if we had one bit to spare for every cons representation we could do use that bit to mark conses as been touched and abort the ordinary equal if we find a mark. For x86-64 we have one such bit available which is cool. My sugestion is to implemen those two versions and we well then not see a performans
degradation unless on 32bit platforms with treelike structures
Stefan
Den 3 sep 2012 00:08 skrev "Ludovic Courtès" <address@hidden>:
>
> Hi,
>
> Stefan Israelsson Tampe <address@hidden> skribis:
>
> > The cycle detection for a tree would probably look something like,
>
> Tortoise-and-hare would have to be applied to arbitrary data structures, AIUI.
>
> Ludo’.
>
>
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Ludovic Courtès, 2012/09/01
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Ian Price, 2012/09/02
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, David A. Wheeler, 2012/09/02
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Stefan Israelsson Tampe, 2012/09/02
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Ludovic Courtès, 2012/09/02
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?,
Stefan Israelsson Tampe <=
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Mark H Weaver, 2012/09/08
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Stefan Israelsson Tampe, 2012/09/08
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Alex Shinn, 2012/09/08
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Mark H Weaver, 2012/09/08
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, William ML Leslie, 2012/09/10
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Stefan Israelsson Tampe, 2012/09/09
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Stefan Israelsson Tampe, 2012/09/03
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Ludovic Courtès, 2012/09/03
- Re: Will guile support R7RS terminating "equal?" in the presence of cycle?, Stefan Israelsson Tampe, 2012/09/04