[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: queue-length should be O(1) ?
This page is part of the web mail archives of SRFI 117 from before July 7th, 2015. The new archives for SRFI 117 contain all messages, not just those from before July 7th, 2015.
- To: srfi-117@xxxxxxxxxxxxxxxxx
- Subject: Re: queue-length should be O(1) ?
- From: Takashi Kato <ktakashi@xxxxxxxxx>
- Date: Wed, 03 Dec 2014 19:13:29 +0100
- Delivered-to: srfi-117@xxxxxxxxxxxxxxxxx
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ymail.com; s=s2048; t=1417630403; bh=jGxdv+zCyNXc/qLSY8jFxRBOXb5Wo7tMPwrAn4cvAvw=; h=Date:From:To:Subject:References:In-Reply-To:From:Subject; b=j5o2hxvcccxmsY7AOYW+qhYjoC+PDUc/mpaGKV3ZXsI53NdbBrW55z9y8wR+TgnJuJunYW1S+5nEr5yxYsokTkNRodHTg4lro/orJxWoFG86K/UiFs9Tw31VhpcXs/u0vxHM/7jez8BwTuJGVvB7Sjc5nbq3Yl0VyaR44mwg1Q1uuxu7IaZ2CQKmZNICqwPvZClaqryQ4cMPpk333jyYzbpcPapJxrcaFP/h1s2pg3u03X6uFCMKJDyz4QZlf2VFEh6IUZn2KrpbwxsOlY/YUPw0aRt7il+nCW64wOpzknuHIkB2XUFeoQXvUNg6tlkwQg1ZdTnsKxzc5XxIXpYYFA==
- Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=s2048; d=ymail.com; b=jnVz6s5VeTuQeKXenjgpDoP/RsFe7vooW6mY7LpYcTFvGd8MjfwVnAyiBj1cx0CgYUFyv9r4zpxKR2LbMvjCyfdF1U2YgUy2GNLQLSg+MDslcgQQIu9pRlPY5c3sthCCP+zKa3iO3/17v6hXrtbAwpbvWcucJHOMJ43vOrzx+WsILcxfPT7Fz+M938jZkrrNrusAvRq+cCVtAWpucASrKkBSx1tailKJ85nBSpPssM6TGF69L8KyNuIwIXa9+7I//aHyWRBnAabwv/6mVbKTN7RXbhKt1CpeOXlEP0mgjZabUk6kJRfKAY6ztj+ZNh7sMu5TfI5HH8WQKW8aD9xbVA==;
- In-reply-to: <20141203131906.GA29310@mercury.ccil.org>
- References: <20141203.092501.756592971992382910.hartrumpf@gmx.net> <20141203131906.GA29310@mercury.ccil.org>
- User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
You trade off adding a mutation for every element added and removed to the
queue for speeding up queue-length. I suspect that's not a good trade.
I suspect queue-empty? is far more likely to be used, and that's fast.
Isn't it, then, better not to specify the order so that implementation
may choose how it's implemented at least for this particular procedure?
Or do the orders indicate worst cases?
_/_/
Takashi Kato
E-mail: ktakashi@xxxxxxxxx