make a hash table (or array) be in strictly ascending order?
in [Lisp]
|
Prev: USOCKET::%SETUP-WAIT-LIST is undefined.
Next: FlateDecode, ASCIIHexDecode, ASCII85Decode, and LZWDecode streams
From: Krzysztof Drewniak on 26 Jun 2010 11:15 Suppose I have a hash table {#\a =>1 #\b => 2 #\c => 3 #\e =>5} (perl notation, for lack of anything better) where element #\d has been removed by a previous operation. I would like to force that hash table to be in strict ascending order (#\a #\b #\c #\d) as opposed to (#\a #\b #\c #\e) (with element #\e having moved to #\d, without losing the value). How would I accomplish this? I see no function to do this? Krzysztof Drewniak -- X-Real-Email-With-Antispam: krzysdrewniak at gmail dot com pgp key on keyserver.ubuntu.com and maybe some other place too
From: Krzysztof Drewniak on 26 Jun 2010 11:30 Krzysztof Drewniak <krzysdrewniakNOSPAM(a)gmai.com> writes: > Suppose I have a hash table {#\a =>1 #\b => 2 #\c => 3 #\e =>5} (perl > notation, for lack of anything better) where element #\d has been > removed by a previous operation. I would like to force that hash table > to be in strict ascending order (#\a #\b #\c #\d) as opposed to (#\a #\b > #\c #\e) (with element #\e having moved to #\d, without losing the > value). How would I accomplish this? I see no function to do this? > > Krzysztof Drewniak Never mind. I realized I don't even need to do this for things to work. Krzysztof -- X-Real-Email-With-Antispam: krzysdrewniak at gmail dot com pgp key on keyserver.ubuntu.com and maybe some other place too
From: Pascal J. Bourguignon on 26 Jun 2010 12:47 Krzysztof Drewniak <krzysdrewniakNOSPAM(a)gmai.com> writes: > Suppose I have a hash table {#\a =>1 #\b => 2 #\c => 3 #\e =>5} (perl > notation, for lack of anything better) where element #\d has been > removed by a previous operation. I would like to force that hash table > to be in strict ascending order (#\a #\b #\c #\d) as opposed to (#\a #\b > #\c #\e) (with element #\e having moved to #\d, without losing the > value). How would I accomplish this? I see no function to do this? The data structure you are describing is NOT a hash-table, for two reasons: - you're asking for order. hash-tables don't impose any order on the keys. - you're asking to change the association between key and value, while it's the ESSENTIAL FEATURE of a hash-table to make an eternal link between a key and a value (even if it may be changed from time to time, betwee t0 and t1, the link between k1 and v1 will exist between t0 and t1 of all eternity). So why are you talking us about hash-tables? What about this abstract data structure: (make-strange-map lessp) --> strange-map (strange-map-add-key strange-map new-key value) --> strange-map (strange-map-insert-value strange-map key new-key value) --> strange-map (strange-map-delete-value strange-map key value) --> strange-map (strange-map-map strange-map fun) --> void with: ----(strange-map.lisp)---------------------------------------------------------- ;;;; -*- mode:lisp;coding:utf-8 -*- ;;;;************************************************************************** ;;;;FILE: strange-map.lisp ;;;;LANGUAGE: Common-Lisp ;;;;SYSTEM: Common-Lisp ;;;;USER-INTERFACE: NONE ;;;;DESCRIPTION ;;;; ;;;; Strange-map for Krzysztof. ;;;; Programmed as a functional data structure. ;;;; And release under the BSD license, be happy! ;;;; ;;;;AUTHORS ;;;; <PJB> Pascal J. Bourguignon <pjb(a)informatimago.com> ;;;;MODIFICATIONS ;;;; 2010-06-26 <PJB> Created. ;;;;BUGS ;;;;LEGAL ;;;; BSD ;;;; ;;;; Copyright Pascal J. Bourguignon 2010 - 2010 ;;;; ;;;; Redistribution and use in source and binary forms, with or ;;;; without modification, are permitted provided that the following ;;;; conditions are met: ;;;; ;;;; 1. Redistributions of source code must retain the above ;;;; copyright notice, this list of conditions and the ;;;; following disclaimer. ;;;; ;;;; 2. Redistributions in binary form must reproduce the above ;;;; copyright notice, this list of conditions and the ;;;; following disclaimer in the documentation and/or other ;;;; materials provided with the distribution. ;;;; ;;;; 3. The name of the author may not be used to endorse or ;;;; promote products derived from this software without ;;;; specific prior written permission. ;;;; ;;;; THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY ;;;; EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, ;;;; THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A ;;;; PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR ;;;; BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, ;;;; EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED ;;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, ;;;; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ;;;; ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT ;;;; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING ;;;; IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF ;;;; THE POSSIBILITY OF SUCH DAMAGE. ;;;;************************************************************************** (defstruct (strange-map (:constructor %make-strange-map)) lessp (keys (vector)) (values (vector))) (defun make-strange-map (lessp) (%make-strange-map :lessp lessp :keys (vector) :values (vector))) (defmethod print-object ((self strange-map) stream) (print-unreadable-object (self stream :identity t :type t) (format stream ":lessp ~S" (strange-map-lessp self)) (loop :for key :across (strange-map-keys self) :for value :across (strange-map-values self) :do (format stream " (~S . ~S)" key value))) self) (defmacro with-strange-map-slots ((lessp keys values) strange-map &body body) (let ((vstrange-map (gensym))) `(let* ((,vstrange-map ,strange-map) (,lessp (strange-map-lessp ,vstrange-map)) (,keys (strange-map-keys ,vstrange-map)) (,values (strange-map-values ,vstrange-map))) ,@body))) (defun strange-map-count (strange-map) (length (strange-map-keys strange-map))) (defun strange-map-equalp (strange-map) (let ((lessp (strange-map-lessp strange-map))) (lambda (a b) (and (not (funcall lessp a b)) (not (funcall lessp b a)))))) (defun strange-map-has-key-p (strange-map key) (find key (strange-map-keys strange-map) :test (strange-map-equalp strange-map))) (defun strange-map-ref (strange-map key) (let ((pos (position key (strange-map-keys strange-map) :test (strange-map-equalp strange-map)))) (if pos (aref (strange-map-values strange-map) pos) (error "Key ~S is not in the strange map ~S" key strange-map)))) (defun strange-map-add-key (strange-map new-key value) " RETURN: A new map with all the (k v) associations from STRANGE-MAP, and with the new pair (NEW-KEY VALUE) added. The NEW-KEY must not already exist in STRANGE-MAP. PRE: (strange-map-has-key-p strange-map new-key) is false POST: (eql (strange-map-ref (strange-map-add-key strange-map new-key value) new-key) value) " (with-strange-map-slots (lessp keys values) strange-map (let ((old-pos (position new-key keys :test (strange-map-equalp strange-map))) (size (strange-map-count strange-map))) (when old-pos (error "Key ~S already exists in strange map ~S" new-key strange-map)) (let ((old-pos (position-if (lambda (old-key) (funcall lessp new-key old-key)) keys)) (new-keys (make-array (1+ size))) (new-values (make-array (1+ size)))) (if old-pos (progn (replace new-keys keys :end2 old-pos) (replace new-keys keys :start1 (1+ old-pos) :start2 old-pos) (setf (aref new-keys old-pos) new-key) (replace new-values values :end2 old-pos) (replace new-values values :start1 (1+ old-pos) :start2 old-pos) (setf (aref new-values old-pos) value)) (progn (replace new-keys keys) (setf (aref new-keys size) new-key) (replace new-values values) (setf (aref new-values size) value))) (%make-strange-map :lessp lessp :keys new-keys :values new-values))))) (defun strange-map-insert-value (strange-map key new-key value) " RETURN: With key_l be the smallest of key and new-key according to (STRANGE-MAP-LESSP STRANGE-MAP), with key_m be the smallest of key and new-key according to (STRANGE-MAP-LESSP STRANGE-MAP), a new map with all the associations (k v) from STRANGE-MAP when k<key_l or key_m<k and with (k_i v_i+1) when key_l < k <= key_m if key < new-key or with (k_i+1 v_i) when key_l <= k < key_m if new-key < key and with (key value). EXAMPLES: STRANGE-MAP: 02 04 06 08 10 12 14 a b c d e f g 06 11 x 02 04 06 08 10 11 12 14 a b x c d e f g 06 03 x 02 03 04 06 08 10 12 14 a b c x d e f g PRE: (strange-map-has-key-p strange-map new-key) is false POST: (eql (strange-map-ref (strange-map-add-key strange-map key value) key) value) " (with-strange-map-slots (lessp keys values) strange-map (let* ((size (strange-map-count strange-map)) (equalp (strange-map-equalp strange-map)) (old-pos-old (position key keys :test equalp)) (old-pos-new (position new-key keys :test equalp))) (unless old-pos-old (error "Old key ~S does not exist in strange map ~S" key strange-map)) (when old-pos-new (error "New key ~S already exists in strange map ~S" new-key strange-map)) (let ((old-pos-new (position-if (lambda (old-key) (funcall lessp new-key old-key)) keys)) (new-keys (make-array (1+ size))) (new-values (make-array (1+ size)))) (if old-pos-new (progn (replace new-keys keys :end2 old-pos-new) (replace new-keys keys :start1 (1+ old-pos-new) :start2 old-pos-new) (setf (aref new-keys old-pos-new) new-key)) (progn (replace new-keys keys) (setf (aref new-keys size) new-key))) (replace new-values values :end2 old-pos-old) (replace new-values values :start1 (1+ old-pos-old) :start2 old-pos-old) (setf (aref new-values old-pos-old) value) (%make-strange-map :lessp lessp :keys new-keys :values new-values))))) (defun strange-map-delete-value (strange-map key) " RETURN: A new strange-map with all the associations (k v) from STRANGE-MAP when k < key according to (STRANGE-MAP-LESSP STRANGE-MAP), and with (k_i v_i+1) for key <= k. NOTE: The last key and the value at the old KEY are removed. " (with-strange-map-slots (lessp keys values) strange-map (let ((old-pos (position key keys :test (strange-map-equalp strange-map))) (size (strange-map-count strange-map))) (unless old-pos (error "Key ~S does not exists in strange map ~S" key strange-map)) (let ((new-keys (make-array (1- size))) (new-values (make-array (1- size)))) (replace new-keys keys :end2 (1- size)) (replace new-values values :end2 old-pos) (replace new-values values :start1 old-pos :start2 (1+ old-pos)) (%make-strange-map :lessp lessp :keys new-keys :values new-values))))) (defun strange-map-map (strange-map fun) (loop :for key :across (strange-map-keys strange-map) :for value :across (strange-map-values strange-map) :do (funcall fun key value)) (values)) (let ((sm (strange-map-add-key (strange-map-add-key (strange-map-add-key (strange-map-add-key (strange-map-add-key (make-strange-map (function char<)) #\a 1) #\b 2) #\c 3) #\d 4) #\e 5) )) (terpri) (princ "Before: ") (print sm) (let ((sm (strange-map-delete-value sm #\d))) (terpri) (princ "After: ") (print sm) (terpri))) #|| Before: #<STRANGE-MAP :lessp #<SYSTEM-FUNCTION CHAR<> (#\a . 1) (#\b . 2) (#\c . 3) (#\d . 4) (#\e . 5) #x0003347ABFF0> After: #<STRANGE-MAP :lessp #<SYSTEM-FUNCTION CHAR<> (#\a . 1) (#\b . 2) (#\c . 3) (#\d . 5) #x0003347B1A30> ||# ;;; Local Variables: ;;; eval: (cl-indent 'with-strange-map-slots 2) ;;; End: -------------------------------------------------------------------------------- -- __Pascal Bourguignon__ http://www.informatimago.com/
From: Tim X on 26 Jun 2010 20:47 Krzysztof Drewniak <krzysdrewniakNOSPAM(a)gmai.com> writes: > Suppose I have a hash table {#\a =>1 #\b => 2 #\c => 3 #\e =>5} (perl > notation, for lack of anything better) where element #\d has been > removed by a previous operation. I would like to force that hash table > to be in strict ascending order (#\a #\b #\c #\d) as opposed to (#\a #\b > #\c #\e) (with element #\e having moved to #\d, without losing the > value). How would I accomplish this? I see no function to do this? > > Krzysztof Drewniak If I understand you correctly, I think your trying to impose an order on a data structure which isn't correct. A hash table is not an ordered collection. Even in perl, it is not guaranteed that the keys of a hash table are in any order. Strictly speaking, in a hash table, the key is passed through a hashing function that determines the key based on the input provided. Frequently, the value returned is just the value passed in, but it does not have to be. There is no guarantee regarding the order keys and values are stored in a hash table or even on how that table is represented 'under the hood'. This provides a number of interesting possibilities For example, I might be working in a domain where I have data with known properties that would make the default hashing inefficient - either it would create hash tables which are too sparse and larger than necessary or perhaps my data will have lots of collisions, which I don't want or perhaps I know something about how the data will be accessed and I want to organise the table in an order that will make retrieval faster. In this situation, I might define a new hashing function that reduces the size of my hash table or reduces collisions or organises the data in the table in an order that is optimised for how I will retrieve it. That new hashing function might do this by storing the data in a different order to what one might expect based on the keys used as input. Sometimes, the values used as keys in your hash table don't have a 'natural' or defined sort order or perhaps the sort order varies depending on things like locale etc. Even in simple default cases, it is possible that a language implementation will return a list of keys in a non-sorted form because that is faster than returning them sorted. Unless a language specification clearly defines the sort order of keys returned by a function, you cannot rely on that order. The normal approach is to pass the keys returned through a sorting function. Frequently, you will explicitly define the characteristics of that sorting function. Tim -- tcross (at) rapttech dot com dot au
From: Giovanni Gigante on 27 Jun 2010 12:19
Tim X wrote: > Even in perl, it is not guaranteed that the keys of a hash > table are in any order. By the way, for these cases there is an idiom in perl in which one keeps the table in an array, and builds an anonymous hash on the fly when the associative mapping is needed. While this is not really an ordered hash, it works like one, and it just uses the builtins. $ my @a = ('one' => 1, 'two' => 2); $ARRAY1 = [ 'one', 1, 'two', 2 ]; $ +{@a}->{'one'} 1 The leading '+' is a syntactic hint of the infamous "Do What I Mean" kind. If one likes this rather wasteful idea, one can easily build something similar in CL. g |