Nowe posty

Autor Wątek: Operacje na bitach.  (Przeczytany 1273 razy)

Offline 1709

  • Users
  • Guru
  • *****
  • Wiadomości: 2757
  • 1709
    • Zobacz profil
Operacje na bitach.
« dnia: 2019-08-07, 12:39:59 »
W chwili obecnej mam tylko 1GB wolnej pamięci RAM.
Ma to znaczenie gdy chce np. otworzyć plik danych 2 GB.

Zgaduje ze otwarcie w ten sposób pliku jest nie możliwe.
Pomyślałem ze sobie sam zapisze dane i będę się w nim poruszał jak w nieskończonym świecie minecrafta.
Czyli otwierając plik,  tylko w określonej lokalizacji pliku, z określoną ilością danych.

Ale czy da się taki plik z poziomu basha stworzyć?
Musiałbym chyba mieć możliwość zapisania danych w określonym miejscu na dysku.
PS: Brak polskiej czcionki, nie jest to brak lenistwa, a jej brak w systemie i brak czasu na reczne poprawki.

Offline Paweł Kraszewski

  • Administrator
  • Guru
  • *****
  • Wiadomości: 3047
  • Lenistwo jest matką potrzeby = babcią wynalazku
    • Zobacz profil
Odp: Operacje na bitach.
« Odpowiedź #1 dnia: 2019-08-10, 06:21:13 »
Dla mnie otworzyć to otworzyć. Plik może mieć i 100TB, ale otwarcie go nie robi nic, co mierzalnie zwiększyłoby zajętość pamięci (pewnie kernel zajmie 1 stronę, 4kB, albo i nie).

Inna sprawa to wczytać cały plik do pamięci. No tu nic nie zrobisz.

* Co to za plik, że z Basha po nim jeździsz? Jakiś tekst, czy binarka?
* Jakie naprawdę operacje na nim chcesz robić (bo że wczytać całość do RAM to już wiemy)

Co do dostępu z poziomu basha do wielkiego pliku binarnego: możesz używać polecenia dd do czytania fragmentu pliku od bajtu X o długości Y bajtów i do nadpisania bloku w istniejącym pliku od bajtu Z.

Co do dostępu do wielkich plików z poziomu "normalnych" języków, do tego służy mmap, otwierasz plik i mapujesz go do pamięci jako tablicę. I tu jest magia, on nie musi się mieścić w pamięci, kernel sam ładuje do przestrzeni wirtualnej fragmenty, do których piszesz i czytasz, potencjalnie usuwając fragmenty, do których nie odnosiłeś się przez jakiś czas (takie LRU).
Jak masz struktury (np C) stałej długości i bez wskaźników (czyli struktura zawiera w sobie wszystkie dane i są tylko elementu typu char imie[32] a nie ma żadnych typu char * imie), to możesz zmmapować tablicę takich struktur na plik i mieć taką bieda-bazę danych indeksowanych integerem.
Paweł Kraszewski
~Arch/Void/Gentoo/FreeBSD/OpenBSD/Specjalizowane customy

Offline 1709

  • Users
  • Guru
  • *****
  • Wiadomości: 2757
  • 1709
    • Zobacz profil
Odp: Operacje na bitach.
« Odpowiedź #2 dnia: 2019-08-10, 12:34:26 »
Cytuj
Co to za plik, że z Basha po nim jeździsz? Jakiś tekst, czy binarka?
Plik tekstowy.

Cytuj
Jakie naprawdę operacje na nim chcesz robić (bo że wczytać całość do RAM to już wiemy)
Przepraszam ze nie podałem skryptu, ale nie chciałem podawać skryptu, bo mogę być źle odebrany.
A żeby opisać całość, muszę się trochę rozpisać.
Napisałem sobie skrypt do generowania słownika wyrazów / słów składających się z liczb 0 i 1.
Bedzie mi on potrzebny do wygenerowania sum kontrolnych.
Użyje przed skryptem polecenie time.
Im szybciej algorytm / suma kontrolna poradzi sobie ze słownikiem, to znaczy ze jest szybszy.
Teoretycznie żeby ładnie ocenić prędkość algorytmu (~1GB/s)
wystarczy wygenerować słownik danych o wielkości np. 1GB.
Z małymi danymi to bez sensu bo algorytmy mogą być porównywalnie szybkie, czyli granica błędu pomiarowego, więc mógłbym źle to zmierzyć.
Udało mi się stworzyć słownik o wielkości 88MB,
potem musiałem wyłączyć komputer, bo przestał prawie reagować,  bo skrypt zajął całą  pamięć RAM.

Oczywiście mogę
- sobie stworzyć dodatkowe SWAP jako RAM
- podzielić słownik na osobne pliki
- mogę każdy ciąg zapisywać w osobnym pliku,
 to idealne rozwiązanie dopóki sam ciąg nie przekroczy ~1GB.
I nie wiem co jeszcze mogę.
- aa mógłbym sobie stworzyć bazę danych, może ona nie będzie wczytywać aż tyle?
ale nie wiem w czym będzie najlepiej

No ale stwierdziłem ze zawsze będę miał z tym problem bawiąc się ogromnymi plikami.
Np. Logi.
- Kiedyś niechcący log internetowy stworzyłem ~50GB.
- Na innym systemie gdzie system wykrywa więcej RAM, log od gry Warframe wczytuje 1 min.
Zwłaszcza ze bawiąc się danymi mogę na tym 1GB nie poprzestać.


Wracając do skryptu basha. Generuje on od najmniejszego ciągu aż do określonego za poleceniem skryptu
czyli
$ bash ./rec 2
generuje mi słownik o długości znaków 2, czyli coś takiego
0
1
00
01
10
11

1. Nie dałem tutaj tworzenia słownika a-z, ponieważ
dla mnie w tym momencie było rozgryzienie
Jak bardzo kolizyjne są algorytmy jeśli chodzi o długość ciągu danych.
Skoro napisałem wcześniej skrypt podobny do AIDA, który nigdy w 100% nie da pewności ze plik nie został nadpisany.
Ze względu na występujące kolizje z dużymi plikami. To warto sprawdzić który algorytm jest lepszy.
Czyli musiałem stworzyć słownik o coraz dłuższym ciągu i porównać. 
2. Dlatego wystarczyłby słownik a-b, ale stwierdziłem że może bash / komputer poradzi sobie jeszcze szybciej
 jeśli podam mu to w 0 i 1 ( chociaż nie wiem czy potraktuje to jak bity z których są zbudowane litery )

Gdy tylko próbnie sprawdziłem
$ bash ./rec 40
który wygenerował wspomniany wcześniej plik o 88MB zajmując RAM ~1GB
Oczywiście zgaduje ze chodzi o otwarcie pliku
- bo plik ma podobna wielkość
- bo wątpię by np.  zapamiętanie ciągu  30 znaków ciągu było dla komputera problemem,
 gdy ja się tu rozpisuje o wiele bardziej :D
Zwłaszcza ze wyżej w przykładzie widać ze skrypt generuje bardzo duża ilość wierszy, a to tylko 2 znaki.
No chyba ze są jakieś wzory matematyczne, które zrobią to bez tworzenia słownika ...?

Zeby sprawdzić te kolizyjności musiałbym wygenerować dla niego słownik od najkrótszego wzwyż.
Dla przykładu:  MD5 to 128-bitowy skrót. ( a ja nawet do 40 nie doszedłem :D )

Teraz nie znajdę, ale widziałem też przykład sposobu graficznego, coś w stylu
https://i.pinimg.com/736x/24/d2/82/24d2829bb665b1f1199a818803ea6a72.jpg
O tym tez będę musiał poczytać jak to się robi.

No ale tak czy siak, może kiedyś jak znajdę czas, pobawię się C / C++ , tym wspomnianym mmap,
bo jak nie do tego, to pewnie taki plik przyda mi się do czegoś innego.

A zastanawiając się jakby to mogło działać
- W przykładzie wyżej tylko dopisywałem ciąg do pliku, wiec to nie powinien być problem.
Ale gdybym chciał dopisywać gdzieś na początku lub w środku pliku to przesuwanie danych w dużym pliku mogło by trwać zbyt długo.
Czyli format pliku w każdym, powiedzmy  " wierszu " musiałby uwzględnić ewentualny skok ( jak "jump" w asm :D )
A później ewentualnie można plik "defragmentować" ( czyli układać jego prawidłową kolejność ).
Chociaż wczytując mala ilość danych z pliku, może to zbędne.
No i tu tez mógłby się pojawić problem ze kiedyś taki powiedzmy jeden " wiersz " pliku może zając 1 GB RAM
No i tego ograniczenia już chyba nie da się zmienić :D

 
dd faktycznie fajne :D
https://unix.stackexchange.com/questions/121794/read-the-middle-of-a-large-file

Edytowane
Co do skryptu sie pomylilem,
moze jednak go podam

#!/bin/bash
echo "Long word: $1"
BASE={0..1}

for WORD1 in `seq 1 $1`; do
#echo $WORD1
OUT="${OUT:+$OUT}$BASE"
#echo $OUT
for WORD2 in  $( eval echo $OUT ); do
echo "$WORD2" >> base${1}
done
done
Samo " echo "$WORD2" >> base${1} " nie powoduje wzrostu pamieci RAM, wiec chyba bash za duzo chyba czegos zapamietal.
Ale fakt faktem gdy probuje recznie otworzyc plik, to zużycie RAMU nagle wrasta :D

Edytowane
Znalazlem takie pytanie odnosnie for (petli)   https://lists.gnu.org/archive/html/bug-bash/2010-09/msg00103.html
« Ostatnia zmiana: 2019-08-10, 18:21:00 wysłana przez 1709 »
PS: Brak polskiej czcionki, nie jest to brak lenistwa, a jej brak w systemie i brak czasu na reczne poprawki.

Offline Paweł Kraszewski

  • Administrator
  • Guru
  • *****
  • Wiadomości: 3047
  • Lenistwo jest matką potrzeby = babcią wynalazku
    • Zobacz profil
Odp: Operacje na bitach.
« Odpowiedź #3 dnia: 2019-08-10, 20:29:34 »


W BASH-u robisz takie rzeczy in-memory???

#!/usr/bin/env bash

BITS=${1:-8}
shift

if [ "$1" ]; then
DICT="$@"
else
DICT="0 1"
fi

next_gen() {
local PREV=$1
local THIS=$2

if [ "$PREV" -a -f "$PREV" ]; then
# Jest poprzednia generacja, powiel ją po kolei z każdym
# elementem słownika
for S in $DICT; do
sed "s/^\\(.*\\)\$/$S\\1/" "$PREV" >> "$THIS"
done
else
# Nie ma - zacznij od słownika
for S in $DICT; do
echo $S >> "$THIS"
done
fi
}

PREV=""

# Pojedź kolejne generacje
for THIS in $(seq -w $BITS); do
next_gen "part_${PREV}.txt" "part_${THIS}.txt"
PREV=$THIS
done

# Zrób jeden plik z wynikiem
cat part_*.txt > dict.txt
rm -f part_*.txt
i teraz
./gen.sh   # generacja ciągów 1..8 bitów
./gen.sh  4 # generacja ciągów 1..4 bitów
./gen.sh  10 # generacja ciągów 1..10 bitów
./gen.sh  4 a b c # generacja ciągów 1..4 znakowych kombinacji  słownika a b c
./gen.sh  6 0 1 2 3 4 5 6 7 8 9 A B C D E F  # generacja ciągów 1..6 cyfrowych liczb szesnastkowych
ostatni:
> time ./gen.sh 6 0 1 2 3 4 5 6 7 8 9 A B C D E F

46,22s user 0,13s system 99% cpu 46,364 total

> ls -al dict.txt
-rw-r--r--  1 pawel  pawel  124076832 10 sie 20:26 dict.txt

> wc -l dict.txt
 17895696 dict.txt
Paweł Kraszewski
~Arch/Void/Gentoo/FreeBSD/OpenBSD/Specjalizowane customy

Offline Paweł Kraszewski

  • Administrator
  • Guru
  • *****
  • Wiadomości: 3047
  • Lenistwo jest matką potrzeby = babcią wynalazku
    • Zobacz profil
Odp: Operacje na bitach.
« Odpowiedź #4 dnia: 2019-08-10, 21:44:36 »
Można np tak (Rust stable):
use std::{
    fs::File,
    io::{BufWriter, Result, Write},
};

fn add_data<W>(f: &mut W, dict: &str, len: u8, prefix: &str) -> Result<()>
where
    W: Write,
{
    // Po kolei dla każdego znaku słownika
    for i in dict.chars() {
        // Wpis składa się z dotąd wyliczonego przedrostka i znaku słownika
        let curr = format!("{}{}", prefix, i);

        if len <= 1 {
            // Jeżeli to ostati znak danego "słowa", zapisz je do pliku
            writeln!(f, "{}", curr.as_str())?;
        } else {
            // Jeżeli nie, wywołaj rekurencyjnie ze słowem jako prefiksem
            add_data(f, dict, len - 1, curr.as_str())?;
        }
    }
    Ok(())
}

fn main() -> Result<()> {
    // Pomijamy args(0) (nazwa pliku)
    let mut args = std::env::args().skip(1);

    // jak w ogóle nie ma len to ustawiamy na 8, jak jest na sparsowany string
    let len = args
        .next() // Następny element args
        .unwrap_or("8".to_string()) // Jeżeli nie ma, to zastąp 8-ką
        .parse::<u8>() // Sparsuj jako u8
        .expect("Bledna dlugosc"); // Jak się nie uda sparsować, wyświetl błąd

    // jak w ogóle nie ma dict to ustawiamy na "01", jak jest na podany string
    let dict = args
        .next() // Następny element args
        .unwrap_or("01".to_string()); // Jeżeli nie ma, to zastąp "01"

    // Nazwa pliku zawiera max długość i słownik
    let fname = format!("dict_{}_{}.txt", len, dict);

    // Otwieramy buforowany plik wyjściowy
    let mut file = BufWriter::new(File::create(fname)?);

    // Jedziemy długości od 1 do len włącznie (to ten = po ..)
    for clen in 1..=len {
        add_data(&mut file, dict.as_str(), clen, "")?;
    }
    Ok(())
}
i test (tutaj słownik podajemy bez spacji!)
> time target/release/rust_dict_gen 6 0123456789ABCDEF
2,91s user 0,05s system 99% cpu 2,963 total

> ls -al dict_6_0123456789ABCDEF.txt
-rw-r--r--  1 pawel  pawel  124076832 10 sie 21:39 dict_6_0123456789ABCDEF.txt

> wc -l dict_6_0123456789ABCDEF.txt
 17895696 dict_6_0123456789ABCDEF.txt

Paweł Kraszewski
~Arch/Void/Gentoo/FreeBSD/OpenBSD/Specjalizowane customy