Hacker News Reader

Comment by moss2 | Hacker News Reader

What is the N*M problem? I can't find anything on google (except a scientific figure behind a paywall).

Before Unix, there were multiple types of files in an OS, Text files (sequential access), Random access, Random Access - Indexed, Databases, etc... and the OS required you to use a different library to access each type of file.

So if you wanted to be able to do N things (grep, word count, sort) across these M file types... you had to write N*M functions, each a bit different.

Unix simplified this to having everything as a text file (a special case of a file of bytes). This made it possible to have a set of N tools that could work on any part of the system, instead of 1/Mth of it.

The pipe operation allowed tools to be composed, you could grep, then word count, etc. This greatly increased the amount of computation that could be expressed as a task straight from the command shell, without having to write new tools.

If you have N things producing data, and M things consuming data, you have a problem where each of the M consumers needs to handle all N types of input data, meaning you have to implement N*M things. But if you have a "narrow waste", meaning a common interface like JSON that all N things are capable of producing and all M things are capable of consuming, then you only need to implement N+M things (N things that produce JSON, and M things that consume JSON).

But you still have to do some validation and presumably some type checking.

So this redistributes the problem instead of solving it.

JSON is a file and interchange format - more technically a protocol.

It is not a data type.

> JSON is a file and interchange format - more technically a protocol.

> It is not a data type.

Although me, and I'm sure many others, have abused JSON and used it as a data type, I totally agree with you. However, GP was using JSON as an example of a more general idea. I needed to aggregate similar data across many different tables holding information collected from web scraping - typically one table corresponds to a particular service, and each service has it's own spider. My approach was to define a data model that contains all the information that I care about then write classes per service to convert its data to the format of the aforementioned data model. While the model can be serialized as JSON, it's composed of standard Python data types/classes and I don't constrain its design to be more amicable to serialization. Point being, while JSON is an intuitive example and can be a good go-to if your data matches it well, there's many ways to solve the N*M problem in this particular context.

Heh it’s narrow waist (think thin point) but I like your term better.

An example of a narrow waist would be CSV - everything can export it, most things can import it, and you can usually fix whatever errors were introduced.

It also sucks bigtime.

Best example I know of:

You have M languages, and N computer architectures. You want a compiler from every language to every architecture, but don't want to write M*N compilers.

One solution is to make a virtual machine. Now, you write M language-to-VM compilers, and N VM-to-cpu compilers, so you only have to write M+N compilers.

For example - if you wrote a new language that targeted the JVM it’d “out of the box” work on almost all systems.

The reality is of course more complicated but the idea is there.

thats like webassembly these days :D

Reply on news.ycombinator.com