It would be nice if instead it collected all of the atoms in the string appends into a tree structure, flattened the tree structure, and then applied string append to the flattened list. Or instead if a lazy evaluation is present, the implementation could translate:
(string-append (string-append "a" "b") (string-append "c" "d"))
to
(string-append "a" "b" "c" "d")
and so on, until the actual string value is needed.
>>9
Do you mean have sexp->html return a list of strings and then (apply string-append lst) to it? I can see how that might make the code easier to read, but traversing a tree is already inefficient, and traversing a list in addition to that would be Terrible! I assume that string-append is much faster than append as well.
If anybody has any optimization tips, let me know. I'm thinking of writing a blog and maybe even a text board in pure Scheme with S-exps as the templates and markup.
>>11
No, pure Scheme. No frameworks or non-standard implementation dependent shit, except getenv which is necessary for CGI and seems to be included with most implementations anyway.
class EnterpriseConcatExample {
public static String concat(String[] strings) {
StringBuilder acc = new StringBuilder();
for(String string : strings) {
acc.append(string);
}
return acc.toString();
}
}
In the first example, there are many unneeded strings produced by the string concatenations. In fact, the first one takes \Omega(n^2) time. Whereas the second collects the strings in an ordered list, and then finally concatenates all of them once they entire collection is assembled. When all the strings are known at the time of the concatenation, the length of the final string is known, and the buffer can be allocated and each string copied once into its place. Thus, the entire operation can be done in linear time.
Your application is more complex than these example. In the examples a flat list is translated into a single string, whereas you must translate a tree of strings into a single string. You are right in that flattening a tree using append will be inefficient. A custom routine could be used for this though. It's hard to write though. I'll post it when I'm done.
>>14 the problem with using nested calls of string append is that there is unneeded copying.
Ah, you're right. It's kinda like the ''.join(strs) vs. for str in strs: result += str debate in FIOC. It just slipped my mind. I'll change the implementation.
yeah, it is sneaky. It's fairly easy to flatten a tree is you use a mutable stack and recursion, but I'm trying to write a functional version. I might finish soon... It's complicated and it could be slow...
>>16
I managed to flatten the tree in one climb without append by using quasiquotes. Not sure if that has the same performance issues but it feels noticeably faster than it was.
yeah, this cuts out the string appends, so there is savings there. The quasiquote @ basically have the same functionality as append, so there are appends going on. The appends can be made optimal if the list data structure can find the back of the list in a single step and if they can be destructively appended to each other, but this isn't the case in when using conses in scheme.
In the above, the '(1 2) '(3 4) lists are not really needed. If they are destructively modified to create the '(1 2 3 4) then the work to create them is useful for the final result, but if the '(1 2 3 4) list is a new copy, then the intermediate '(1 2) and '(3 4) lists aren't necessary.
I have something using delay and force. I'll post it once I work out the bugs.
(define (test)
(let ((data '((((test test test)
test
(test test)
data
(data data (test)))
(nested data test)
test)
(data data data test test (t) (((t))) (t test test)))))
(display (apply string-append
(llist->list (lmap1 symbol->string
(flatten-ltree (tree->ltree data))))))))
>>24
I don't know, it wasn't obvious to me how to express it in a purely functional way. But I'll try it that way. I think it can be done easier that way a lot easier than >>25 actually. It would need to be a recursive procedure that takes both the tree and the current state of the stack as a parameter, and then the new state of the stack would be returned. It's actually pretty natural.
(define (test)
(let ((data '((1) data data data (data data (data) (data) (data) (((data)))) (data data))))
(display (reverse (flatten-tree data '())))))
Of course there are multiple solutions that all mean something different:
Name:
Anonymous2013-08-31 14:44
If my rather charismatic Bard rolls 1d20+8 for a gather information check, it takes 1d4+1 HOURS to complete. So does that mean I can't do anything else for christ knows how many turns?! Surely by that time the party would have moved on!
Name:
Anonymous2013-08-31 15:30
There is now a 1.54 patch. Also there is a patch to update from 1.50 to 1.54 (and from 1.52 to 1.54 if you have the DL version).
This update adds a third version of the "Secret Basement", the dungeon that generates random items in your inventory each floor.
Name:
Anonymous2013-09-01 14:35
In accordance with the traditional view of Aristotle, the Hellenistic Greeks generally preferred to distinguish the potential infinity from the actual infinity; for example, instead of saying that there are an infinity of primes, Euclid prefers instead to say that there are more prime numbers than contained in any given collection of prime numbers (Elements, Book IX, Proposition 20).