5 ms·

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

by moss2 4y ago

deleted 4y ago
[deleted]
chrisshroba 4y ago
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).
- deleted 4y ago
  [deleted]
- TheOtherHobbes 4y ago
  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.
  - jmt_ 4y ago
    > 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.
- bombcar 4y ago
  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.
hoosieree 4y ago
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.
- bombcar 4y ago
  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.
- thgs 4y ago
  thats like webassembly these days :D
mikewarot 4y ago
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.

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

by moss2 4y ago

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

deleted 4y ago

[deleted]

chrisshroba 4y ago

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).

deleted 4y ago
[deleted]
TheOtherHobbes 4y ago
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.
- jmt_ 4y ago
  > 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.
bombcar 4y ago
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.

hoosieree 4y ago

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.

bombcar 4y ago
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.
thgs 4y ago
thats like webassembly these days :D

mikewarot 4y ago

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.