jbapple

31 ms·

241.
by jbapple 15y ago
I think that "second-order lambda-calculus" usually refers to system F, which doesn't even have dependent types. What I'm getting at is that there are plenty of parts of GHC's flavor of Haskell that you can't depend on type inference for. Y
242.
by jbapple 15y ago
> Whatever plans you've had for the last year, you didn't throw yourself into them. How do you know?
243.
by jbapple 15y ago
Eugene, Oregon, internship possible, noremote On Time Systems is a small company (about 22 employees) that develops AI applications for scheduling and routing. We're currently looking for software engineers to work on Green Driver (a smartp
244.
The ACM and me (on refusal to publish arXived public domain papers)(r6.ca)
2 points by jbapple 15y ago|0 comments
245.
by jbapple 15y ago
The string b-tree also does trie-like search without sacrificing balance: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.59...
246.
by jbapple 15y ago
Good points. Given a query string of length k and cache lines that store B bits, the crit-bit trie for the bad input uses Theta(k) computations and causes Theta(k) cache misses, I think. A balanced tree holding the same set causes Theta(k *
247.
by jbapple 15y ago
> Does the treap balancing mechanism not result in a tree equivalent to what one would get permuting the input sequence with "order by rand()"? I'm pretty sure it does. Yes, it does, but I was responding to you comment that "expected lo
248.
by jbapple 15y ago
> Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data. Consider a crit-bit tree over variable-length bit strings. The set 1, 11, 111, ... (with n bi
249.
by jbapple 15y ago
> I believe, but haven't verified, that expected logarithmic height is achieved just by randomly permuting the input sequence and not doing any subsequent balancing - so the treap approach is simply deferring the permuting to insertion
250.
by jbapple 15y ago
> That said, their definition of optimal is big-O, There are balanced search trees with shorter maximum height, but they often take asymptotically longer for local operations (finger update and finger search). > which is unimpressiv
251.
by jbapple 15y ago
> I've never understood the allure of treaps. Ignoring the simplicity argument, treaps can perform some other operations (local updates and nearby searches) in optimal expected time (see theorems 3.1 and 3.2): http://sims.berkeley.edu/
252.
by jbapple 15y ago
I thought top trees were a data structure for implementing "dynamic trees" or "link-cut trees". How can they be used for implementing search trees? Do the logarithmic update times in top trees take into account the time to locate the node t
253.
by jbapple 15y ago
> There's a standard trick for representing trees with the 2-3-4 invariant using non-regular data types: It should be noted that this puts a Theta(lg n) singly-linked list of Succ nodes at the top of the tree, thus doubling the effectiv
254.
by jbapple 15y ago
Deletion is trickier: http://matt.might.net/articles/red-black-delete/ I suspect treap delete is simpler.
255.
by jbapple 15y ago
> And I believe prior to this one, the early 90s recession had been the worst since WWII. I disagree: http://en.wikipedia.org/wiki/List_of_recessions_in_the_Unite... The three recessions immediately preceding the early 90s recession
256.
by jbapple 15y ago
Eugene, Oregon, internship possible, noremote, H1B applicants welcome. On Time Systems is a small company that develops scheduling, routing, and other AI applications. We're currently looking for software engineers to work on Green Driver (
257.
by jbapple 15y ago
Eugene, Oregon, internship possible, noremote, H1B applicants welcome. On Time Systems develops scheduling, routing, and other AI applications. Right now we're looking for engineers for our pilot and driver routing applications. We are acti
258.
by jbapple 15y ago
Eugene, Oregon - fulltime - noremote - H1B applicants welcome On Time Systems is a small company that specializes in solving large-scale search and optimization problems. We used to be a research lab at the University of Oregon, but we are
259.
by jbapple 15y ago
They displayed my email address in plain text on a world-readable page, so I tried to delete my account, but that feature is not available yet. Failed solutions display the output of your program run, but do so incorrectly by eliminating l
260.
by jbapple 15y ago
Eugene, Oregon - fulltime - H1B applicants welcome On Time Systems is a small company that specializes in solving large-scale search and optimization problems. We used to be a research lab at the University of Oregon, but we are now more f
261.
by jbapple 15y ago
Cache-oblivious streaming B-trees: http://supertech.csail.mit.edu/papers/sbtree.pdf I don't know for certain any open-source implementation, but I have heard COLAs are used in HBase.
262.
by jbapple 15y ago
I had a sdf.lonestar.org account. Once, when their mail servers appeared to me to be down for a day, I asked on the discussion forums if I was the only one experiencing problems. The site administrator posted a response right away on the fo
263.
by jbapple 16y ago
GADT are really cool, but I would like to note three caveats: 1. > in lines 13..21, an AVLTree type is defined -- with its invariants encoded in the type system Its balance invariants are encoded, but its ordering invariants are not. 2.
264.
by jbapple 16y ago
I didn't apply a few months ago (when I was looking) because of that one line. I'm glad to hear that you're not becoming burnt out!
265.
by jbapple 16y ago
I'd like to hear more about this line from their job listings: http://www.quora.com/jobs "You should be ready to make this startup the primary focus of your life" That could mean a wide range of things - from social engagement and occasio
266.
by jbapple 16y ago
> That you can finger-append in O(u) is misleading, since ideally u≃log n What's finger-append? > finger operations are amortized O(1) in AVL trees (I know it's been shown empirically, not sure if analytically) Do you have a citatio
267.
by jbapple 16y ago
> Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures where operations return a new immutable copy of the structure, but share mo
268.
by jbapple 16y ago
I don't find skip lists to be simpler than AVL trees, but it's my understanding I'm in the minority on this issue. What I do find very interesting about skip lists is that they support fingers - pointers to locations in the structure that a
269.
by jbapple 16y ago
> I was looking for standard tree algorithms like AVL trees What did you need to use AVL trees for that std::set/std::map could not provide?
270.
by jbapple 16y ago
Can you explain in more detail what you were looking for? > I once emailed Dr. Bjarne Stroustrup about this; more precisely non-existence of even simple tree algorithms from C++ standard library. He just pointed me to implementation of

More ›