xgboost memory problem
Memory is shortage in xgboost program
Sometimes, program is forcibly quit when using xgboost. In that time, there are several solutions(It is true that the solution is existed except for the following).
https://www.kaggle.com/c/grupo-bimbo-inventory-demand/discussion/22321
solution
use the external memory version http://xgboost.readthedocs.io/en/latest/how_to/external_memory.html
Try bagging sklearn.ensemble.BaggingRegressor — scikit-learn 0.18.1 documentation
AtCoder Beginner Contest 060 D - Simple Knapsack
Problem Statement
You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi.
You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.
Your objective is to maximize the total value of the selected items.
Constraints
1≤N≤100 1≤W≤109 1≤wi≤109 For each i=2,3,…,N, w1≤wi≤w1+3. 1≤vi≤107 W, each wi and vi are integers.
how to solve
We have to check the constraints. In this problem w and v is big, so we cannot solve this problem in common dynamic programming way. This time we use the constraint w1 ≤ wi ≤ w1 + 3. Because of this, there are at most 4 possible weights for a single item. So I can test the all case that is how many items I have to use per 4 weights. This time complexity is O(n4)
code is following
Build Order
problem
You are given a list of projects and a list of dependencies ( which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.
how to solve
This problem is topological sort. Topological sort algorithm is the following approach.
- Identify all nodes with no incoming edges and add those nodes to our topological sort.
- When we do the above, decline the number of incoming edges as the out coming from the added node.
- Repeat the above, When all the nodes have been added to the topological sort, then we done.
This algorithm is executed in time complexity O(V + E).
code
Paths with Sum
problem
You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
how to use
If I can check the all path I can find the solution in O(n2). So I suggest the optimized one. In the optimized code, I use hash-table like two sum problem. This hash-table maps from a runningSum to the number of times we’ve seen that sum. In each node, I can find the count of root path to satisfy the condition in O(1) . So time complexity is O(n) and space complexity is O(n) to have a hash table.
code
Check Subtree
problem
T1 and T2 are two very large binary trees, with T1 much bigger than T2. Create an algorithm to determine if T2 is a subtree of T1. A tree T2 is a subtree of T1 if thre exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
how to solve
I prepare two function. One is the function to determine if the 2 tree is same or not, and the other one is the function determine if the t1 is the subtree of t2. First function is implemented to check if all element is same or not recursively.
code
return k-th to last
problem
Implement an algorithm to find the kth to last element of a singly linked list
how to solve
We use two pointers slow-pointer and fast-pointer. Firstly we proceed the fast-pointer in k step. Secondly, we move them at the same pace and slow pointer will hit the end of the linked list after k length . This algorithm takes O(n) time and O(1) space.
code
Atcoder Grand Contest : B Splatter Painting
problem
how to solve
The limitation of d is very small and it is key point to solve this problem. Consider that dp[v][i] which means “paint dp[v][i] among the range d distance from vertex v”. The time complexity is O(d(n+m) + q)
