DanWaterworth

AFAIK, planting more trees by itself doesn't really help in the long term, because trees eventually decompose releasing the carbon they captured.

Inference in this context means getting the output of a neural network on some input. Training meaning adjusting a neural network to so that it's outputs are more like the training data.

Training involves finding derivatives and requires higher precision calculations which is why they don't train using TPUs.

Myrtle Software | Software Developer | Cambridge, UK | ONSITE FULLTIME INTERNS https://myrtlesoftware.com

We're looking for developers to work on our compiler that generates hardware to accelerate convolutional neural networks.

* Experience with functional programming is essential (we use Haskell for everything),

* Familiarity with with hardware design would be beneficial,

Drop us an email at jobs@myrtlesoftware.com if you're interested and there's more information at https://myrtlesoftware.com/vacancies/

It needs to be spine strict for that to work, but the amortization for finger trees doesn't work without laziness

When you need that kind of behaviour, you can't replace it with something flat (without doing binary searches or similiar at each crossing). Sometimes intrusive lists are the right thing.

I built something once that used intrusive skiplists because it needed to expire elements using one ordering and search them by another. It would have been much less efficient if I'd have broken it up into multiple flat representations.

(Actually, it was flat, but explaining that aspect of it is quite difficult).

I don't know how the kernel is using intrusive lists, but that kind of traversing and switching is occasionally useful.

You can't necessarily replace intrusive linked lists with arrays. They have more operations. You can traverse so far in one list then switch to traversing in another.

The problem with using lazy data structures for storing things is that deletes don't necessarily free up storage. Fingertrees are fine when you need to store a collection in order to implement some algorithm (and being persistent makes it useful if this algorithm has to backtrack), but they aren't so good for backing a collection that changes over time, like the set of currently connected sockets in a network service.

> belief in things not empirically testable or verifiable and that science.

Sorry to nitpick, but science isn't verifiable, it's falsifiable. Also, there are religious people who'd agree with your characterisation of faith and there are others who wouldn't.

So did religion.

Modern science came out of religion. To believe that they are in direct opposition is unbelievably narrow.

IANAL, but that's not how I read the FAQ or the license:

    4.6 Access to Derivative Databases. If You Publicly Use a Derivative
    Database or a Produced Work from a Derivative Database, You must also
    offer to recipients of the Derivative Database or Produced Work a copy
    in a machine readable form of:

          a. The entire Derivative Database; or

          b. A file containing all of the alterations made to the Database or
    the method of making the alterations to the Database (such as an
    algorithm), including any additional Contents, that make up all the
    differences between the Database and the Derivative Database.

    The Derivative Database (under a.) or alteration file (under b.) must be
    available at no more than a reasonable production cost for physical
    distributions and free of charge if distributed over the internet.

> Either way, this aspect is independent of the point I was making above and which is that functional code is not inherently easier to test than procedural code.

That's true, you can certainly just write procedural code in functional languages and there's no benefit. However, you also have the ability to structure code in a way that is testable and is actually more structured than the equivalent OOP style. By which I mean: the operations on the dependencies are more constrained (since they can't be replaced or duplicated, etc).

When you do dependency injection well, you don't inject every object; that would be horrible/impossible. What you may have noticed is that there are two kinds of objects, ones that you inject and ones that you don't. The ones you don't are things like numbers, strings and maps/sets; things that you treat as values. The other objects do things, I tend to call them services.

In order to do a straight-forward conversion to functional programming, I suggest leaving the values as they are and each service becomes a free monad transformer. So, instead of having a logger, you have a logging monad transformer that has a log instruction. Instead of having a database, you have a database monad transformer that has a query instruction, etc.

You are then free (no pun intended) to replace the interpreters of these free monads during testing with whatever mock implementation you please and the result is a more principled dependency injection inspired style.

Actually, I would constrain the monad type via type classes, rather than using free monads, but the approaches are equivalent.

I stand corrected.

This is interesting. It doesn't mention GC, but since frozen objects can be shared between guilds, I assume the GC remains global. Perhaps this will trigger interest in immutable datastructures in ruby.

Right, you're assuming there's one tree being maintained.

Thanks, I see. Are you assuming ephemeral usage of nodes to make that claim?

Re-read the article, bearing in mind that O(sqrt n) is a set that contains O(1).

I don't know where you got those numbers from.

It's roughly right, but it's not cache obliviousness that enables the violation. For the argument to work out, you have to evaluate it within a model that has an explicit cache and hence, treats big O results as being parametrized over the cache width.

> It has nothing to do with the model and is just a question of whether b is a variable in the big O notation.

There are models, like the cache oblivious model, where b is assumed to be a variable, so the model matters.

> a binary tree and b-tree stay within a constant factor even as you vary b.

it's not a constant factor if b is a variable. It's a factor of log b.

> Sorry cache-misses don't count as part of a theoretical analysis on complexity.

They don't in the random access machine model, but there are other models where cache misses do factor in.

> O(log_b(n)) is the same as O(log n)

Not in every abstract model. See other reply.

Which is why you have to evaluate in a model with an explicit cache width. In such a model, b is not a constant. The cache-oblivious model [1] is a fairly well-known example, but that won't work in this case, since we need to know b to set the tree width. Any of the other external memory models will do.

[1] https://en.wikipedia.org/wiki/Cache-oblivious_algorithm

You have to evaluate it in a model with an explicit cache width size, then O(log_b(n)) < O(log(n))

It doesn't hold for binary tree lookups vs B-tree lookups.

> if Oi(f(N)) > Oi(g(N)), Ot(f(N) will be > Ot(g(N)).

That doesn't hold. Some instructions take longer than others.

There are models like the Transdichotomous model [1], where the properties of the machine vary based on the problem. That seems to be what is happening here.

[1] https://en.wikipedia.org/wiki/Transdichotomous_model

> You'll know that iterating through a linked list is O(N), binary search is O(log(N)) and a hash table lookup is O(1). What if I told you that all of the above is wrong?

It's not wrong, it doesn't have enough contextual information to be right or wrong.