Jump to content

Wikipedia:Reference desk/Archives/Computing/2017 July 9

From Wikipedia, the free encyclopedia
Computing desk
< July 8 << Jun | July | Aug >> July 10 >
Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


July 9

[edit]

Line Mode Browser?

[edit]

I am interested in running Line Mode Browser on the latest version of Windows 10. Has anyone ported it? Failing that, has anyone ported it to an environment that has an emulator for Windows 10? I can't find a compiled version that runs on anything. Yet the image on our Line Mode Browser page shows that someone managed to read Wikipedia using it... --Guy Macon (talk) 12:10, 9 July 2017 (UTC)[reply]

If you have a 32-bit version of Win10, you can try the 2002 distribution. It fails on a 64-bit version. Ruslik_Zero 21:00, 9 July 2017 (UTC)[reply]
I was able to run comline.exe on Windows 10 x64. The installer in the above location will not run properly, as it uses a 16 bit Installshield. A very common problem with old applications that affects all x86-64 versions of Windows including XP and also ReactOS. (Just do a search for 16 bit installer and probably all results will be about the issue.) If you run it, it should extra the install files into a temporary directory before Windows tells you it can't run. You can then follow these instructions [1]. It seems to be Installshield 3 so assuming you trust Toastytech you can get a replacement 32 bit installer here [2]. If you don't well trust them, well I doubt the LMB really needs to be installed so you just have to find some way of extracting the files. Or alternatively install it on a VM and recover the files. (In that case you don't even have to use Toastytech, just some version of windows with support for 16 bit executables.) Note that the screenshot was from 2010. I doubt you can access wikipedia anymore simply since it went HTTPS only and I'm pretty sure the above version doesn't support HTTPS. You could of course use some sort of HTTPS to HTTP proxy. Nil Einne (talk) 06:12, 10 July 2017 (UTC)[reply]
Thanks! I am expecting a lot of things not to work. Running a browser that old is a lot like teaching a dog to walk on his front two legs or asking a politician to give you a straight answer; the wonder is not that he does it well, but that he does it at all. :) --Guy Macon (talk) 06:27, 10 July 2017 (UTC)[reply]

A desired software(s)

[edit]

I wish to type datas in the PC than transfer it to the Smart Phone, vice versa (also wish to type in the Smart Phone than transfer it to the PC), off-line. Could you refer me to any apps that could be synchronised using WiFi and or as well as Bluetooth in order to perform stated task

The following is what I seek: MS Outlook’s Calender, Tasks, Notes, Contacts.

Note: I’ve used many apps but ‘writing on PC than transferring it to the Smart Phone, also writing it on the Smart Phone than transfer it to the PC’ is a desired thing, what I’m unable to find. Could you refer me to something good please?

116.58.201.114 (talk) 15:52, 9 July 2017 (UTC)[reply]

Your question is too broad. There are a lot of ways to synchronize information between a smart phone and a PC. You can use, for instance, Google drive. Ruslik_Zero 20:48, 9 July 2017 (UTC)[reply]
Google Drive need on-line connection plus I'm not happy with it...
Okay:
Please refer me to an app(s) for creating "Tasks" and "Notes" - which consists of similar functionalities like MS Outlooks Tasks and Notes - that I could use or write, modify, amend, delete things in it in PC than transfer it to the Smart Phone using WiFi without internet on-line issue, also vice verse (i.e., write, modify, amend, delete things in it in the Smart Phone than transfer it to the PC using WiFi without internet on-line issue). 116.58.200.35 (talk) 16:33, 10 July 2017 (UTC)[reply]

Running quantiles - does this 'enriched' binary search tree have a name?

[edit]

I am a hobby programmer, and I do not know all the terms of a pro computer scientist.

I have been thinking about the problem of maintaining k running quantiles, say over a window of. e.g., n = 8192 samples as computationally and memory efficient as possible. The samples coming in are quite unordered.

I realize, that if I only had to maintain a single running quantile, such as the running sample median, a good procedure would be to maintain a max-heap and a min-heap as priority queues, where the max-heap would be used for adding and removing elements with a values less than or equal to the current median, and the min-heap would be used for adding and removing elements with values larger than the median. By keeping track on the number of values added to either heap, elements can then be transferred along the way between the two heaps to assure they contain an equal number of elements (min heap one less for uneven sample sizes) and their roots can be used to find the median.

If I want to maintain k running quantiles, e.g., 10%, 20%,..., 90% (k=8). I could allocate k min-heaps and k max-heaps using k x n x sizeof(element) storage.

However, I am looking for an efficient solution, where I do not have to scale the memory and heap operations by a factor of k 'just' because I want to maintain k concurrent running quantiles.

For that purpose I tried to look into maintaining an 'enriched' binary search tree, where each node besides left and right references also has low and high references to nodes, which would refer directly to the next and previous nodes in a sorted list of all nodes, wothout having to traverse the tree in a classical tree search. This is convenient because the current quantiles can be maintained as k pointers to nodes containing the k running quantile values. If supplemented by counters to maintain how many elements are in the tree with values below each of the k quantile nodes, the quantiles can be maintained by moving it to quantile.high, if the sample count below the node becomes too small. Or point to quantile.lo if the number of sample points below the quantile node exceed the sample quantile.

It is not that hard to maintain the extra low/high pointers. I made a prototype implementation is Python where I just add values and maintain just a running median this way, and it seems to work. Here I have just the code for maintaining the 'enriched' BST tree when adding elements in order to not make things too complicated.

class Node:
    
    def __init__(self, data, lo=None, hi=None, left=None, right=None):
        self.data = data
        # Number of data values added
        self.count = 1
        # Linked list to Node with next lower value if all nodes were sorted
        self.lo = lo
        # Linked list to Node with next higher value if all nodes are sorted
        self.hi = hi
        # Node in binary search tree, with a lower value
        self.left = left
        # Node in binary search tree with a higher value
        self.right = right
        # If left and right nodes are None, the node is a leaf in the BST
        
            
class Tree:
    
    def __init__(self):
        self.root = None
        
    def add(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            current = self.root
            while True:
                if data < current.data:
                    if current.left is None:
                        nd = Node(data, lo=current.lo, hi=current)
                        if current.lo is not None:
                            current.lo.hi = nd
                        current.lo = nd
                        current.left = nd
                        break
                    else:
                        current = current.left
                elif data > current.data:
                    if current.right is None:
                        nd = Node(data, lo=current, hi=current.hi)
                        if current.hi is not None:
                            current.hi.lo = nd
                        current.hi = nd
                        current.right = nd
                        break
                    else:
                        current = current.right
                elif data == current.data:
                    current.count += 1
                    break

    def remove(self, data):
        ...

Now, this implementation is slow because

  1. I need to allocate new/delete objects every time I add data
  2. Creating objects in Python is just much slower than maintaining heapyfied lists

However regarding allocation, a fixed memory area of size n x sizeof(node data structure) could just be preallocated and a queue be maintained to keep track of vacant indices of nodes. Secondly this does not need to be implemented as objects, but can be maintained as lists of tuples of a fixed format.

As far as I can see adding/deleting a node is O(log(n)) (assuming the tree is fairly balanced, which is a reasonable assumption as the data I have in mind are unsorted on reception) and finding the lower/higher sorted element is O(1), so this seems very efficient for maintaining the k quantiles in O(log(n) + k) time.

I am sure I am not the first to consider such an 'enriched' binary search tree.

Does this kind of sequentially sorted binary search tree have a name?

Is there a better way to solve the same problem of maintaining k running quantiles?

-- Slaunger (talk) 20:42, 9 July 2017 (UTC)[reply]

In my opinion, memory is cheap, so store all the data in memory (you do it as heaps, but I would do it as an array). You can do an insertion sort as data comes in. Then, the 10th percentile is index floor(X/10) where X is how many items you've inserted. I do a lot of percentile queries on very large data sets (more than 10 million entries, often more than 100 million entries). My solution is consistently to sort and then hit index floor(X/10), floor(2X/10), floor(3X/10), floor(4X/10), etc... Sort is O(n log(n)). You claim your add/delete is O(log(n)) and you do it for n items. So, your overall algorithm is O(n log(n)). In both cases, hitting a specific index is O(1). So, I don't see a benefit to making a bunch of heaps when I could simply sort all of the data. 209.149.113.5 (talk) 13:30, 10 July 2017 (UTC)[reply]
Another way I could phrase my response, which may make more sense is to imagine smaller and smaller heaps in your solution, allowing more percentile calculations. Eventually, you will have one item per heap. You will have a sorted array. Your algorithms is just an insert sort, so why not insert sort a sorted array and you can pick out any percentile you want, such as the 23.7th percentile. 209.149.113.5 (talk) 15:17, 10 July 2017 (UTC)[reply]
And a comment about big O notation: It's a good first approximation of how efficient an approach will be, but then bench-marking shows which is really best. The "overhead" that's often neglected when using big O notation, such as allocating and deallocating memory, can be significant. StuRat (talk) 17:41, 10 July 2017 (UTC)[reply]

Javascript forum

[edit]

Hello. I am coding some Javascript and I keep hitting a roadblock. Is there a forum somewhere that will allow me to post the troubling code and someone will tell me what I am doing wrong?    → Michael J    22:52, 9 July 2017 (UTC)[reply]

You can post it here, but the most popular site for such questions is Stack Overflow.—Best Dog Ever (talk) 23:30, 9 July 2017 (UTC)[reply]
Another alternative is [the codereview subsite of stackexchange.]--Hofhof (talk) 13:04, 10 July 2017 (UTC)[reply]