diff options
author | Kaz Kylheku <kaz@kylheku.com> | 2017-11-15 06:19:49 -0800 |
---|---|---|
committer | Kaz Kylheku <kaz@kylheku.com> | 2017-11-15 06:19:49 -0800 |
commit | 8230a637a32ce0c88ba1c51aeb6c2d5edcece109 (patch) | |
tree | f8580dade862468172873b42cd1aaf82b3676478 | |
parent | 6f7c75ed060f3c824740cf0a471be4a235f2fe51 (diff) | |
download | txr-8230a637a32ce0c88ba1c51aeb6c2d5edcece109.tar.gz txr-8230a637a32ce0c88ba1c51aeb6c2d5edcece109.tar.bz2 txr-8230a637a32ce0c88ba1c51aeb6c2d5edcece109.zip |
find-if: optimized rewrite and hash support.
* lib.c (find_if): Function rewritten to use the seq_info
sequence classification mechanism, for much better
performance on vector-like objects. Also, supports hash
tables just like find_max.
* txr.1: Documentation updated regarding hash support
of find-if.
-rw-r--r-- | lib.c | 57 | ||||
-rw-r--r-- | txr.1 | 16 |
2 files changed, 63 insertions, 10 deletions
@@ -8594,19 +8594,58 @@ val find_min(val seq, val testfun, val keyfun) return find_max(seq, default_arg(testfun, less_f), keyfun); } -val find_if(val pred, val list, val key) +val find_if(val pred, val seq, val key) { - key = default_arg(key, identity_f); - list = nullify(list); + val keyfun = default_arg(key, identity_f); + seq_info_t si = seq_info(seq); - gc_hint(list); + switch (si.kind) { + case SEQ_NIL: + break; + case SEQ_HASHLIKE: + { + val hiter = hash_begin(si.obj); + val cell; - for (; list; list = cdr(list)) { - val item = car(list); - val subj = funcall1(key, item); + while ((cell = hash_next(hiter))) { + val key = funcall1(keyfun, cell); + if (funcall1(pred, key)) + return cell; + } - if (funcall1(pred, subj)) - return item; + break; + } + case SEQ_LISTLIKE: + { + gc_hint(seq); + + for (seq = z(si.obj); seq; seq = cdr(seq)) { + val elt = car(seq); + val key = funcall1(keyfun, elt); + if (funcall1(pred, key)) + return elt; + } + + break; + } + case SEQ_VECLIKE: + { + val vec = si.obj; + val len = length(vec); + val i; + + for (i = zero; lt(i, len); i = succ(i)) { + val elt = ref(vec, i); + val key = funcall1(keyfun, elt); + if (funcall1(pred, key)) + return elt; + } + + break; + } + case SEQ_NOTSEQ: + default: + uw_throwf(error_s, lit("find-if: unsupported object ~s"), seq, nao); } return nil; @@ -27419,7 +27419,7 @@ is returned. .coNP Functions @ find and @ find-if .synb .mets (find < key < sequence >> [ testfun <> [ keyfun ]]) -.mets (find-if < predfun < sequence <> [ keyfun ]) +.mets (find-if < predfun >> { sequence | << hash } <> [ keyfun ]) .syne .desc The @@ -27474,6 +27474,20 @@ element is found, .code nil is returned. +In the case of +.codn find-if , +a hash table may be specified instead of a sequence. +The +.meta hash +is treated as if it were a sequence of hash key and hash +value pairs represented as cons cells, the +.code car +slots of which are the hash keys, and the +.code cdr +of which are the hash values. If the caller doesn't specify a +.meta keyfun +then these cells are taken as their keys. + .coNP Functions @ rfind and @ rfind-if .synb .mets (rfind < key < sequence >> [ testfun <> [ keyfun ]]) |