[Data-modeling] Modeling datastructures

[Daniel Peebles]

I've started implementing the suggestions I've received from this
conversation in my domain. It's looking quite good but I'd welcome
anyone who was interested in helping, as there's a lot of information.
Modeling it on the STL is nice, but the STL creates many unintuitive
types due to C++'s rather strict typing system, that I don't think I'd
put in a knowledge database. That said, people are free to do anything
they want with this stuff :P kinda the point, I guess :)

Built-in MathML (ugh it's verbose, but there's not much else) support
would be very nice. I could construct a compound data type for a full
expression, but it wouldn't be reasonable to expect everyone who
wanted to type an equation to break it down, so it would eventually be
necessary to have a simple "input equation" option that might break it
down internally. Ah well, maybe someday :)

Thanks,
Dan

On Thu, Oct 23, 2008 at 8:37 PM, Faye Harris <faye at metaweb.com> wrote:
> Agreed. It depends on how deep and how detailed you want to model this
> (for example, for search, you would even break it down to best case,
> average case, and worst case scenarios if you're so inclined). I glossed
> over modeling details for an Algorithm type since it was not part of the
> original question.
>
> The whole point of modeling algorithm together with data structure is
> that the complexity of the former depends on the latter, and the two
> types could both share and benefit from topics belonging to an
> complexity order *type* as opposed to just text strings for complexity
> orders that couldn't be reused.
>
> -- Faye
>
>
> Tim Kientzle wrote:
>>> To summarize, this is what we'd have:
>>>
>>> Type: Big O Order (or whatever you want to name it)
>>> Display: Enumerated
>>> Properties:
>>> 1) Data structures with this space complexity (expected type: Data
>>> Structure)
>>> 2) Algorithms with this runtime efficiency (expected type: Algorithm)
>>> Create a topic for each common order: O(1), O(n), O(log n), O(n log
>>> n),
>>> O(n^2), etc.
>>>
>>
>> Actually, there are at least two different complexity measures for
>> each operation on a data structure.[1]
>>
>> So I think you'll need at least a type for operations, another for
>> data structures, and a CVT which attaches a complexity to each
>> combination.
>>
>> E.g.,
>>    array <---  O(n) space ---> Merge sort
>>    array <---  O(n log n) time ---> Merge sort
>>    linked list <--- O(1) space ---> Merge sort
>>    linked list <--- O(n log n) time ---> Merge sort
>>    heap <---  O(n) space ---> inserting n items
>>    heap <---  O(n log n) time ---> inserting n items
>>    heap <---  O(n log n) time ---> removing first n items
>>
>> Of course, as David pointed out, "n" is a pretty simple case.
>> Complexity often varies with several features (average link
>> density, tree height, largest clique).
>>
>> Stepanov's STL work at SGI (http://www.sgi.com/tech/stl/)
>> has resulted in a very nice hierarchy of data structures
>> and operations that seems like a nice starting point for this.
>>
>> Tim
>>
>> [1] Of course, this is only if you limit yourself to big-O
>> asymptotic average complexity.  There are quite a few
>> other complexity measures that are of interest in various cases.
>>
>> _______________________________________________
>> Data-modeling mailing list
>> Data-modeling at freebase.com
>> http://lists.freebase.com/mailman/listinfo/data-modeling
>>
>>
>
> _______________________________________________
> Data-modeling mailing list
> Data-modeling at freebase.com
> http://lists.freebase.com/mailman/listinfo/data-modeling
>